Merge Intervals

Start from brute force

Compare every pair. Build an overlap graph with an edge between any two intervals that intersect, find its connected components, and report each component as [min start, max end]. It is correct because overlap chains are exactly what merges, and the union of a connected run of intervals on a line is one interval. But the pair checks alone are O(n²) time, and storing the edges is up to O(n²) space: at 10⁴ intervals that is about 50 million comparisons. The repeat-until-stable version, which merges any overlapping pair and rescans, is worse, up to O(n³) when each pass finds one merge.

The approach

Sort by start, and the problem collapses to one comparison per interval. The reference merge_intervals returns [] for empty input, then sorts a copy with sorted(intervals, key=lambda iv: iv[0]) and seeds out with list(ivs[0]), a copy so the caller’s data is never mutated. For each later (s, e): if s <= out[-1][1] the interval overlaps or touches the current block, so the block’s end becomes max(out[-1][1], e); otherwise the block is finished and [s, e] starts a new one.

The invariant: out is always the merged answer for the intervals read so far, sorted and non-overlapping, and only its last block can still grow. Every later interval starts at or after that block’s start, while every earlier block ends before it begins, so nothing can reach back past the current block. The <= makes touching intervals merge, and the max keeps a nested interval from shrinking the block. The TypeScript mergeIntervals sorts a copy with (a, b) => a[0] - b[0].

Walk through an example

On the first example the input is already sorted, so the sweep extends one block and then opens two more.

Complexity

Time O(n log n), all of it the sort; the sweep is O(n) with constant work per interval. Space O(n) for the sorted copy and the output; sorting in place would leave only the sort’s own auxiliary space beyond the output. The pairwise overlap graph is O(n²) time and up to O(n²) space for its edges.

Edge cases to test

• [[1, 4], [4, 5]] → [[1, 5]]. Touching intervals merge; a strict < test returns two intervals.
• [[1, 10], [2, 3]] → [[1, 10]]. Setting the end to the new interval’s end instead of the max shrinks the block to [1, 3].
• [[1, 5], [2, 3], [4, 6]] → [[1, 6]]. Comparing with the previous interval’s end (3) instead of the block’s end (5) wrongly splits off [4, 6].
• [[8, 10], [1, 3], [2, 6]] → [[1, 6], [8, 10]]. Unsorted input; sweeping without sorting misses that [1, 3] and [2, 6] overlap.
• [] → []. The reference returns early, before reading ivs[0], which would raise on an empty list.
• [[2, 2], [2, 3]] → [[2, 3]]. A zero-length interval is still an interval and touches its neighbor.

Common mistakes

• Forgetting to sort by start first — the single-pass merge only works on sorted intervals.
• Extending to the next interval’s end instead of max(current, next) — a nested interval then wrongly shrinks the merge.
• Getting the touch case wrong — [1,2] and [2,3] usually merge, so test overlap with ≤.

Follow-ups an interviewer asks next

Insert one new interval into a list that is already merged and sorted.

No sort is needed. Copy the intervals that end before the new one starts, absorb every interval that overlaps it by taking the minimum start and maximum end, then copy the rest. That is one O(n) pass. Binary search can locate the overlapping run in O(log n), but rebuilding a Python list or JavaScript array is still O(n).

Intervals keep arriving. Maintain the merged set as you go.

Keep the merged blocks in a balanced search tree or sorted map keyed by start. On each insert, look up the neighbor just before the new start and the blocks after it, merge every one that overlaps, and remove the absorbed blocks. Each insert is O(log n) plus the merges, and since a block disappears at most once, the merges cost O(log n) amortized.

The intervals are half-open, like calendar slots.

Then [1, 4) and [4, 5) do not overlap, because the first ends exactly when the second begins. Change the test to s < out[-1][1] and keep everything else. The boundary convention is the first thing to confirm in an interview, since it changes the answer on every touching pair.

How many meeting rooms do these meetings need?

That asks for the maximum overlap depth, not the union, so merging loses the answer. Sort the starts and the ends separately and sweep both, adding one at each start and subtracting one at each end, and track the peak; or keep a min-heap of end times. Both are O(n log n).

Where this shows up

Interval merging is the engine behind calendar and booking conflict detection, coalescing IP/CIDR or genomic ranges, and the broader sweep-line family of algorithms. “Sort, then sweep while maintaining a running state” is one of the most reused patterns in scheduling and computational geometry.

Reference solution

def merge_intervals(intervals):
    if not intervals:
        return []
    ivs = sorted(intervals, key=lambda iv: iv[0])
    out = [list(ivs[0])]
    for s, e in ivs[1:]:
        if s <= out[-1][1]:
            out[-1][1] = max(out[-1][1], e)
        else:
            out.append([s, e])
    return out


print(merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]))   # -> [[1, 6], [8, 10], [15, 18]]

function mergeIntervals(intervals: number[][]): number[][] {
  if (intervals.length === 0) return [];
  const ivs = [...intervals].sort((a, b) => a[0] - b[0]);
  const out: number[][] = [[...ivs[0]]];
  for (let i = 1; i < ivs.length; i++) {
    const [s, e] = ivs[i];
    const cur = out[out.length - 1];
    if (s <= cur[1]) cur[1] = Math.max(cur[1], e);
    else out.push([s, e]);
  }
  return out;
}

console.log(mergeIntervals([[1, 3], [2, 6], [8, 10], [15, 18]]));   // -> [[1,6],[8,10],[15,18]]