DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Merge Intervals

mediumIntervals Must-do

Problem statement

You get a list of intervals, each a [start, end] pair. Merge every group of overlapping intervals and return the resulting non-overlapping intervals.

Examples

Example 1

Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]

Output: [[1, 6], [8, 10], [15, 18]]

Explanation: [1, 3] and [2, 6] overlap, so they merge into [1, 6].

Approach

Optimal

Overlaps are hard to spot in random order but easy once the intervals are sorted by start time. After sorting, an interval can only overlap the one you're currently building. If it starts before the current one ends, extend the current one; otherwise, close it and start a new one.

  1. Sort the intervals by their start value.
  2. Start the result with the first interval.
  3. For each next interval, compare its start with the end of the last interval in the result.
  4. If it overlaps (start <= last end), extend the last end to the larger of the two ends. If not, append it as a new interval.
ComplexityTime O(n log n)Space O(n)
Python
def merge(intervals: list[list[int]]) -> list[list[int]]:
intervals.sort(key=lambda iv: iv[0])
merged = []
for start, end in intervals:
if merged and start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end) # overlap: extend
else:
merged.append([start, end]) # gap: new interval
return merged

Frequently asked questions

SREs meet this constantly: merging overlapping maintenance windows before announcing downtime, combining overlapping alerts into one incident timeline, or totalling how long a service was actually down when several outage reports overlap. Google SRE candidates have reported interval questions such as room and time-slot booking.

  • Forgetting to sort first, which makes the single sweep miss overlaps.
  • Setting the merged end to the new interval's end instead of the maximum, which breaks when one interval sits entirely inside another (e.g. [1, 10] and [2, 3]).
  • Treating touching intervals like [1, 2] and [2, 3] differently from what the problem asks. Here they count as overlapping.