Merge Intervals

Merge Intervals is the classic warm-up for the intervals pattern. It teaches the move you reuse for meeting rooms, calendars, and range problems: sort by start time, then sweep once and glue together anything that touches.

The slow way first

You could compare every interval against every other one, repeatedly merging pairs until nothing changes. That is messy and can be O(n²) or worse, and the bookkeeping (which bars are still separate?) is easy to get wrong.

The question to ask: if I lined the intervals up on a timeline, which ones could possibly merge? Only neighbors. And neighbors are obvious the moment everything is sorted by start time.

The idea: sort, then sweep

Sort the intervals by their start. Now walk left to right holding one current merged bar. For each next interval, ask: does its start fall at or before the current bar's end? If yes, the bars overlap — extend the current bar's end. If no, there is a gap — flush the current bar into the output and open a new current bar.

Because the list is sorted, the current bar's end only ever grows, and once we pass it we never look back. One pass does the whole job.

Walk through it

Step through the animation. The top row is the sorted input as timeline bars; the bottom is the single current bar. We open with [1,3]. [2,6] starts at 2, which is ≤ 3, so the bar stretches to [1,6]. Then [8,10] starts past 6 — a gap — so we flush [1,6] and open [8,10]. [15,18] is past 10, so flush again. At the end we flush the last bar.

Pseudocode

sort intervals by start
current = first interval
for each next interval [start, end]:
    if start <= current.end:            # overlap
        current.end = max(current.end, end)   # extend the bar
    else:                                # gap
        append current to merged         # flush it
        current = [start, end]           # open a new bar
append current to merged                 # flush the last bar
return merged

The Python solution

def merge(intervals):
    intervals.sort(key=lambda iv: iv[0])
    merged = []
    current = list(intervals[0])
    for start, end in intervals[1:]:
        if start <= current[1]:
            # overlap: extend the current bar
            current[1] = max(current[1], end)
        else:
            # gap: flush current, open a new bar
            merged.append(current)
            current = [start, end]
    merged.append(current)
    return merged

• intervals.sort(key=lambda iv: iv[0]) orders everything by start time so only neighbors can ever merge.
• current is the bar we are currently growing; we seed it with the first interval.
• start <= current[1] is the overlap test — does the next bar begin at or before where the current one ends?
• On overlap we do current[1] = max(current[1], end); the max matters because a contained interval like [2,4] inside [1,6] must not shrink the end.
• On a gap we append the finished bar and reset current. After the loop we flush the final bar, which is never appended inside the loop.

Complexity

The sort dominates at O(n log n); the sweep itself is linear. The extra space is the output list (plus whatever the sort uses).

When this pattern shows up

Practice