Merge Intervals: The Canonical Sort and Sweep

"Merge Intervals" shows up again and again in Meta, Google, Amazon phone screens. It is a Medium problem on paper, but the real test is whether you recognize the Merge Intervals pattern quickly and code it cleanly. Part 1 of 11 in the Merge Intervals arc.

The Problem

Given an array of intervals [start, end], merge all overlapping intervals and return the non-overlapping result. By published company lists this is one of the most-asked questions at Meta and shows up everywhere else — it is the pattern's namesake for a reason.

Input:  intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]
[1, 3] and [2, 6] overlap and merge into [1, 6].

Recognizing the Merge Intervals Pattern

Interval problems — scheduling, calendars, resource booking — almost all reduce to one move: sort by start (or end), then sweep once while comparing each interval against a running boundary. Overlap exists when the next start is at most the current end. Sort plus linear sweep, O(n log n), is the backbone of the entire family.

Unsorted intervals can overlap arbitrarily, but sorted by start, any overlap must be with the most recent merged interval — nothing earlier can reach forward past it. That single observation turns a quadratic pairwise check into a linear sweep.

The Approach

Sort by start. Seed the output with the first interval. For each next interval: if its start is at most the current end, extend the current end with a max; otherwise push it as a new block.

The max on extension is not optional — [1, 10] followed by [2, 3] must stay [1, 10], and forgetting this is the most common bug in the entire pattern.

Python Solution

def merge(intervals: list[list[int]]) -> list[list[int]]:
    """Merge overlapping intervals. Touching counts as overlapping."""
    intervals.sort(key=lambda iv: iv[0])
    merged: list[list[int]] = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)   # extend, never shrink
        else:
            merged.append([start, end])
    return merged

Complexity

• Time: O(n log n) — the sort dominates; the sweep is linear
• Space: O(n) — the output list (O(log n) auxiliary for the sort)

Interview Tips and Follow-Ups

• Ask whether touching intervals ([1, 4] and [4, 5]) merge — conventions differ and interviewers deliberately leave it ambiguous.
• The envelope case [1, 10] + [2, 3] is the planted test. If your merge writes end instead of max(ends), you fail it.
• Follow-ups to expect: streaming intervals (use Insert Interval's logic) and returning total covered length instead of the list.

More Merge Intervals problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.