Intervals: Sort by Start, Then Merge in One Pass

Once intervals are in order of start, the next one can only overlap the last merged interval, so one pass merges them all.

Merging overlapping intervals takes one sort by start and one pass, comparing each interval only with the last one merged. The cue is a property of the problem: items with a start and an end, and a question about overlap, gaps or how many run at once. An interval [s, e] here is closed, meaning it includes both ends, so [1, 3] contains 3. Five intervals, [4, 7], [1, 3], [8, 11], [2, 5] and [12, 13], are to be merged wherever they overlap.

How many intervals are left after merging?

Three: [1, 7], [8, 11] and [12, 13]. The first, second and fourth chain together, because [1, 3] overlaps [2, 5], which overlaps [4, 7].

Drawn on one axis, the chain is easier to see than in the list, because the list is not in order of start.

text

before merging
          1   3   5   7   9   11  13
[4, 7]          ========
[1, 3]    ======
[8, 11]                 ========
[2, 5]      ========
[12, 13]                        ====
after merging
          1   3   5   7   9   11  13
[1, 7]    ==============
[8, 11]                 ========
[12, 13]                        ====

The invariant is what makes one pass enough: after sorting by start, no later interval begins before the current one, so if the current interval does not overlap the last merged interval, it cannot overlap any earlier one either. Two closed intervals overlap when the next one's start is at most the last one's end, start ≤ last.end, so [1, 3] and [3, 5] touch and merge. Overlap extends the last merged interval to the larger end; no overlap starts a new one. The table walks the sorted list.

Merging the sorted intervals, one at a time
Interval	Compared with	Overlap	Merged list
[1, 3]	None	None	[1, 3]
[2, 5]	[1, 3]	Yes	[1, 5]
[4, 7]	[1, 5]	Yes	[1, 7]
[8, 11]	[1, 7]	No	[1, 7] [8, 11]
[12, 13]	[8, 11]	No	[1, 7] [8, 11] [12, 13]

Each interval is compared once, so the pass is O(n) for n intervals, and the sort before it is O(n log n), which dominates. A wall calendar read in order of start time works the same way: a clash is only possible with the booking last written on the merged list. The likeness breaks at what the reader can see. A person can glance back over the whole day, while the pass looks only at the last merged interval, which is why the order has to be by start.

On the Coding Interview Patterns cheatsheet

← → move through sections and cards