Merge Intervals

Signal

Unordered overlapping ranges that need collapsing is the canonical "sort by start, then sweep" shape — sorting turns an all-pairs overlap question into a single linear scan against just the previous result.

Approach

Sort intervals by start time. Walk through them keeping a running "last merged" interval: if the current interval's start is at or before the last merged interval's end, they overlap — extend the last merged interval's end to cover both. Otherwise, the current interval starts a new group — append it as-is.

Skeleton

sort intervals by start
result = [intervals[0]]
for interval in intervals[1:]:
    if interval.start <= result[-1].end:
        result[-1].end = max(result[-1].end, interval.end)
    else:
        result.append(interval)

Solution

def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda iv: iv[0])
    result = [intervals[0]]

    for start, end in intervals[1:]:
        if start <= result[-1][1]:
            result[-1][1] = max(result[-1][1], end)
        else:
            result.append([start, end])

    return result

Complexity

O(n log n) time — dominated by the sort; the sweep itself is O(n). O(n) space for the sorted copy and result (O(1) extra if sorting in place and merging into it).

Pitfalls

• Comparing only starts and ends of adjacent pairs without sorting first — the overlap check only works because sorting guarantees you never need to look backward past the last merged interval.
• Using < instead of <= for the overlap test — touching intervals like [1,4] and [4,5] are meant to merge in the standard version of this problem.
• Taking max(result[-1].end, interval.end) matters — a later interval can be fully contained inside the current merged range, and blindly overwriting the end with the new interval's end would shrink it incorrectly.