DSA Merging Intervals

The problem

Merge Intervals takes a list of time spans and joins every pair that overlaps. A span is a start time paired with an end time. Two spans overlap when they share at least one moment in time.

The answer is the shortest list of spans that covers the same time. Spans that touch at one moment count as overlapping in this article. Touching means the next start equals the open end.

cases = [
    ([(1, 3), (2, 6), (8, 10), (15, 18)], [[1, 6], [8, 10], [15, 18]]),
    ([(9, 12), (1, 4), (4, 5), (13, 15)], [[1, 5], [9, 12], [13, 15]]),
    ([(5, 7)], [[5, 7]]),
    ([], []),
]
for spans, expected in cases:
    print("spans", spans, "-> merged:", expected)

Read one row at a time. In the first row, (2, 6) starts before (1, 3) ends, so the two join into [1, 6]. In the second row, (1, 4) and (4, 5) only touch at time 4, and they still join.

Intuition: the order of the spans decides what a sweep can see

The first idea sweeps the spans in the order they arrive. One open span stays on the table. Each new span either extends the open span or closes it and opens a fresh one.

That sweep trusts the arrival order. The trust is the trap. A span that starts early can arrive late, after the sweep has already closed the span it belongs to.

def sweep(spans):
    merged = []
    for start, end in spans:
        if not merged or start > merged[-1][1]:
            merged.append([start, end])
        else:
            merged[-1][1] = max(merged[-1][1], end)
    return merged

spans = [(8, 10), (1, 3), (15, 18), (2, 6)]
print("arrival order:", sweep(spans))
print("sorted order:", sweep(sorted(spans)))

The arrival-order sweep swallows (1, 3) into [8, 10] and (2, 6) into [15, 18]. Both spans vanish without extending anything. Sorting by start time is not decoration here. Sorting is what makes the sweep correct.

Brute force: merge any overlapping pair, again and again

The brute force skips the sorting insight. It scans every pair of spans and merges any pair that overlaps. One merge can create a new overlap, so the scan repeats until a full pass merges nothing.

A pair overlaps when each start is not past the other end. The counters below record every pair test and every merge. The counts are the cost, stated in operations instead of seconds.

def merge_brute(spans):
    work = [list(s) for s in spans]
    comparisons = 0
    merges = 0
    changed = True
    while changed:
        changed = False
        for i in range(len(work)):
            for j in range(i + 1, len(work)):
                comparisons += 1
                a, b = work[i], work[j]
                if a[0] <= b[1] and b[0] <= a[1]:
                    work[i] = [min(a[0], b[0]), max(a[1], b[1])]
                    del work[j]
                    merges += 1
                    changed = True
                    break
            if changed:
                break
    return sorted(work), comparisons, merges

merged, comparisons, merges = merge_brute([(8, 10), (1, 3), (2, 6), (15, 18)])
print("merged:", merged)
print("pair tests:", comparisons, " merges:", merges)
merged, comparisons, merges = merge_brute([(1, 2), (4, 5), (7, 8), (10, 11)])
print("no overlaps:", merged)
print("pair tests:", comparisons, " merges:", merges)

The second list is the expensive shape. No pair merges, yet the scan still pays every pair test to prove it. A full pass with no merge is the only way this method learns that the work is done.

The optimal solution: sort, then extend one open span

The open span is the single span still being extended, and sorting by start time before one sweep means every later span either extends that open span or starts after it ends. That one sentence is the whole method.

A new span starts the next open span when its start is past the open end. Otherwise it overlaps or touches, and the open end grows to the larger of the two ends. The end never shrinks, because a short span can sit fully inside a long one.

def merge(spans):
    merged = []
    for start, end in sorted(spans):
        if not merged or start > merged[-1][1]:
            merged.append([start, end])
        else:
            merged[-1][1] = max(merged[-1][1], end)
    return merged

cases = [
    ([(1, 3), (2, 6), (8, 10), (15, 18)], [[1, 6], [8, 10], [15, 18]]),
    ([(9, 12), (1, 4), (4, 5), (13, 15)], [[1, 5], [9, 12], [13, 15]]),
    ([(5, 7)], [[5, 7]]),
    ([], []),
]
for spans, expected in cases:
    result = merge(spans)
    print("spans", spans, "->", result, "expected:", expected, "match:", result == expected)

All four cases pass. No span is ever compared with more than the one open span. The sort lined up every possible overlap in advance.

Walkthrough: merging [(1, 3), (2, 6), (8, 10), (15, 18)]

The walk uses the first case, already sorted. The state is the merged list after each span. The open span is always the last span in that list.

spans = [(1, 3), (2, 6), (8, 10), (15, 18)]
merged = []
for start, end in spans:
    if not merged or start > merged[-1][1]:
        merged.append([start, end])
        print("span", (start, end), "- opens a new span - merged:", merged)
    else:
        merged[-1][1] = max(merged[-1][1], end)
        print("span", (start, end), "- extends the open span - merged:", merged)
print("answer:", merged)

Only the second span extends anything. Its end 6 replaces the open end 3. The last two spans each start past the open end, so each one opens a fresh span and the answer is read straight off the final list.

Complexity

The brute force tests up to n times n minus 1, divided by 2, pairs per pass and may need several passes, so its time is O(n^2) or worse. The optimal sweep sorts in O(n log n) time and then makes one pass, so its time is O(n log n).

The brute force works on a copy of the spans, so its extra space is O(n). The optimal sweep builds the merged list, which holds up to n spans, so its space is O(n).

for n in [4, 8, 16]:
    pairs = n * (n - 1) // 2
    print("spans", n, "- brute pair tests in one pass:", pairs, " sweep steps after sorting:", n)

The gap widens fast. At 16 spans one brute pass already tests 120 pairs against 16 sweep steps. The sort is the price, and the single pass is what it buys.

Edge cases and pitfalls

A span fully inside another span is the classic trap for the open end. Taking the new end blindly would shrink the open span. Taking the larger of the two ends keeps the long span whole.

Touching spans merge in this article. A new span separates only when its start is strictly past the open end. An equality test in the wrong place splits spans that should join.

def merge(spans):
    merged = []
    for start, end in sorted(spans):
        if not merged or start > merged[-1][1]:
            merged.append([start, end])
        else:
            merged[-1][1] = max(merged[-1][1], end)
    return merged

print("empty:", merge([]))
print("single:", merge([(5, 7)]))
print("touching:", merge([(1, 4), (4, 5)]))
print("contained:", merge([(1, 10), (2, 3)]))
print("duplicates:", merge([(2, 4), (2, 4)]))
print("all separate:", merge([(1, 2), (4, 5), (7, 8)]))

The contained row keeps the end at 10. The duplicates row collapses to one span. Each row is the sorted sweep itself, with no special cases added.