Problem 37 · Intervals

Merge Intervals

MediumClassic DSA & systems

01Problem

Given a list of intervals [start, end], merge all overlapping intervals and return the result.

02Key insight

Sort by start; then each interval either extends the last merged interval (start <= last end) or starts a new one.

03Solution

solution.pypython8 lines

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    merged: list[list[int]] = []
    for start, end in sorted(intervals):
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

Try it first.

TimeO(n log n)

SpaceO(n)

tests.py · 4 passing

tests.pypython4 lines

assert merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]) == [[1, 6], [8, 10], [15, 18]]
assert merge_intervals([[1, 4], [4, 5]]) == [[1, 5]]
assert merge_intervals([[1, 10], [2, 3], [4, 5]]) == [[1, 10]]
assert merge_intervals([]) == []

04Staff-level follow-up

Intervals arrive continuously and must stay merged? Keep them in a sorted map (balanced BST / SortedList) and merge neighbors on insert in O(log n) amortized.