Sort and merge intervals

31 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Four time slots: [1,3], [2,6], [8,10], [15,18]. Some overlap. Merge the overlapping ones into single slots. By eye, [1,3] and [2,6] touch, so they become [1,6]; the others stay. Answer: [1,6], [8,10], [15,18].

By hand with many slots, you would compare every pair to see if they overlap, merge, and repeat until nothing changes. For n slots that is n(n − 1)/2 pair checks per round, and a merge can create a new overlap, so several rounds. Messy and slow.

The mess comes from the slots being in random order. If they were in order of start time, an overlap could only happen between a slot and the one right before it, because everything earlier started even earlier.

Build the structure, one piece at a time

Piece 1: sort by start. [1,3], [2,6], [8,10], [15,18] happens to be sorted already.

Piece 2: one current slot. Keep a single slot that is still "open", meaning a later slot might extend it. Start with the first slot, [1,3].

Piece 3: the overlap test. Take the next slot [s, e]. If s ≤ the current slot's end, the two overlap: extend the current end to max(current end, e). Otherwise the current slot is finished: put it in the output and make the new slot the current one.

Why max(current end, e)? A slot like [2,4] after [1,6] overlaps but does not extend; the end must stay 6.

Why it is correct

The invariant: the output slots are disjoint, sorted, and final; the current slot covers every input slot seen so far that is not already in the output; and the current slot's start is at least the output's last end plus a gap.

Because the input is sorted by start, the next slot starts at or after the current slot's start. If it starts at or before the current end, it overlaps and merging keeps the current slot as one connected piece. If it starts after the current end, then every later slot also starts after the current end (they start even later), so nothing will ever touch the current slot again, and it is safe to output it.

sorted by start and s_next > end_current ⇒ s_later ≥ s_next > end_current for every later slot

That one line is the whole proof: sorting turns "could any slot overlap this one" into "does the very next slot overlap this one".

Why it is fast

Sorting n slots costs O(n log n). The sweep looks at each slot once and does a comparison and a max, so O(n).

total = O(n log n) + O(n) = O(n log n)

For a million slots that is about twenty million steps for the sort, versus repeated rounds of five hundred billion pair checks.

How to recognise it in an interview

The cues are "merge", "overlapping intervals", "insert an interval", "free time between meetings", "summary ranges of consecutive numbers". Any input made of [start, end] pairs where the question is about unions or gaps. Say: "Sort by start; then only the previous interval can overlap the next one, so one sweep with a current interval does it."

Merge Intervals is the example above. Insert Interval is the same sweep where one of the slots is new; you can skip the sort if you walk the already-sorted list and merge the new slot in place. Summary Ranges treats consecutive integers as touching intervals of length one.

02The idea in one line

Sort by start; extend the current interval when the next one overlaps.

Reach for it when: Merge, insert interval, employee free time, summary ranges.

Cost: O(n log n) time.

03The walk-through, step by step

The video works one example: Merge Intervals on [[1,3],[2,6],[8,10],[15,18]]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Sort by start; walk left to right keeping one current interval
2. [1,3] starts after the current end: start a new interval
3. [2,6] starts at 2 ≤ 6: overlaps, extend the end to 6
4. [8,10] starts after the current end: start a new interval
5. [15,18] starts after the current end: start a new interval
6. Done: [[1,6],[8,10],[15,18]], disjoint and sorted
7. Sort O(n log n), then one linear sweep

04Asked at Google

9 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Intervals: Sweep line (events ±1), Earliest finish first.