Merge intervals

The problem it solves

Given a pile of ranges — meetings on a calendar, reservations on a resource, byte ranges in a file, IP blocks — collapse every overlapping cluster into one block and return the disjoint union. [1,3], [2,6], [8,10] becomes [1,6], [8,10]. It is the opening move of nearly every interval problem in existence: busy-time computation, free-slot finding, range consolidation in storage engines and genome pipelines, firewall rule normalisation. Interviewers ask it constantly not because it is hard but because it is representative — the sort-then-sweep shape it teaches is the backbone of the whole interval family, and the off-by-one at its boundary (“do touching intervals merge?”) is a specification-reading test disguised as a coding one.

The algorithm is two moves: sort by start, then one pass in which each interval either extends the last merged block or — if a gap separates them — seals that block forever and opens a new one. Everything interesting lives in why that single pass is allowed to be so confident.

The intuition — and where it breaks down

Picture the intervals as bars on a shared timeline — which is literally what the player draws, one row per interval, sorted by start. Read top to bottom, maintaining one “current block”. Each new bar either starts inside (or touching) the block — overlap, so the block absorbs it, its right edge extending if the newcomer reaches further — or starts past the block’s edge — a gap of genuinely uncovered time.

The confident claim, and the second prediction question, is that a gap is permanent: no interval further down the list can ever reach back and bridge it. The sort is the entire justification — every remaining interval starts at or after the current one, and the current one already failed to reach the block. Later starts are larger still; the gap can only be confirmed, never crossed. That one fact — sealed means sealed — is what makes a single pass sufficient, and it evaporates instantly if you forget to sort or sort by the wrong key. Unsorted input turns the problem into repeated scanning; sorted-by-end input breaks the argument entirely.

Where intuition slips: nested intervals. [2,5] arriving while the block is [1,10] overlaps — but extending the end with max(blockEnd, 5) must not shrink the block to 5. The max is not defensive style; it is the difference between right and wrong on any input containing containment, and the nested preset exists to spring exactly this trap. The second slip is the touching boundary: [1,3] and [3,5] merge under start ≤ end (closed intervals) and do not under strict < (half-open). Neither is wrong; not asking which is.

Loading…

A walkthrough you can check

Input [1,3], [2,6], [8,10], [15,18], [16,17], [5,7] — the default preset. Sort by start: [1,3], [2,6], [5,7], [8,10], [15,18], [16,17].

1. [1,3] opens block 1: [1, 3].
2. [2,6]: 2 ≤ 3 — overlap. Block becomes [1, 6].
3. [5,7]: 5 ≤ 6 — overlap by chaining: it never touched [1,3], but the block’s grown edge catches it. Block [1, 7].
4. [8,10]: 8 > 7 — gap. Block 1 sealed at [1,7]; block 2 opens.
5. [15,18]: gap again; block 3 opens. [16,17]: 16 ≤ 18, and max(18, 17) keeps the end at 18 — the nested case, absorbed without shrinking.

Result: [1,7], [8,10], [15,18] — three blocks from six intervals. Step 3 is the one to sit with: transitive overlap through a growing edge is why the comparison must be against the block, not against the original neighbour — a bug the timeline drawing makes visually obvious and flat code does not.

The invariant

The output list is always a set of disjoint, sorted, sealed blocks covering exactly the intervals consumed so far — and only the last block is still live. Each step preserves it: an overlapping interval modifies only the live block’s end (growing it, thanks to max), and a gapped interval seals the live block — permanently correct by the sorted-starts argument — and opens a new live one. No earlier block is ever revisited, which is both the invariant’s claim and the algorithm’s performance.

Termination gives correctness outright: after the last interval, seal the final block; the output covers precisely the union of the inputs (every consumed interval landed in some block that contains it) with no overlaps between blocks (each was opened strictly past its predecessor’s sealed end). The one-directional flow — intervals in, blocks sealed, never reopened — is the property every streaming/interval-sweep algorithm in the family inherits from this template.

Complexity, derived

The sort dominates: O(n log n). The pass is O(n) — one comparison and at most one write per interval — and the output is at most n blocks: O(n) space, or O(1) extra beyond output if the input may be reused. There is no adversarial case hiding anywhere: fully-overlapping input (one giant block) and fully-disjoint input (n blocks, the disjoint preset) cost the same sort-plus-pass.

Could the sort be avoided? Only by paying elsewhere: bucketing by coordinate works when the coordinate universe is small and dense (the timeline-flood referee in this site’s tests does exactly that — a deliberately different method for cross-checking), and pre-sorted input arrives free in many real systems (append-mostly logs, calendar stores), collapsing the whole job to O(n). Saying “if the input is already sorted, this is linear” is the observation that turns a memorised answer into an engineering one.

What people get wrong

• Forgetting max on extension — the nested-interval shrink. The single most common correctness bug, and invisible on inputs without containment.
• Comparing against the previous interval instead of the growing block — breaks transitive chains like step 3 above.
• Sorting by end, or not sorting — the sealed-forever argument dies, and with it the single pass.
• The touching boundary unasked: ≤ versus < changes answers on real data; state the convention aloud before writing the comparison.
• Mutating the input array in place when the caller still needs it — sort a copy, or document the destruction.
• Reaching for this when the question is maximum overlap depth (meeting rooms): that is a sibling sweep over +1/−1 events, not a union — same sorted timeline, different bookkeeping.

Implementation notes

The production shape is exactly the displayed code: sort a copy by start; loop; compare the interval’s start to the last output block’s end; extend-with-max or push. Two disciplined details: extend with max even when it looks unnecessary, and put the touching-intervals convention in one named comparison so the spec decision is visible and changeable.

The family this unlocks, each one edit away: insert interval — the input is already sorted, so binary-search the insertion point and merge locally in O(n); meeting rooms II — sweep +1/−1 events for max concurrency (mind the tie order: ends before starts if touching does not overlap); employee free time — merge everyone’s busy blocks, then read the gaps; interval intersection of two sorted lists — two pointers, advancing whichever ends first. All of them stand on sort-once-sweep-once and the sealed-forever argument; none of them need new ideas, only re-aimed bookkeeping.

On testing: this site referees the sweep against a timeline flood (mark covered points at half-step resolution to catch touching, then read off maximal runs) — a slower, dumber, independent method, which is precisely what makes agreement meaningful. The half-step trick is worth stealing: integer endpoints with touching semantics are exactly the kind of boundary a naive point-marking referee gets wrong.

The follow-up questions

Why does sorting by start license a single pass? Later intervals start later; once a gap appears, nothing downstream can reach back across it. Sealed blocks are final, so the only live state is the last block — O(1) working memory over a sorted stream.

What changes for minimum meeting rooms? That is maximum overlap depth, not union: sort +1/−1 events and track the running count’s peak. Same timeline, different question — confusing the two is the classic interval-family error.

Do [1,3] and [3,5] merge? Closed intervals (<=): yes. Half-open (<): no. It is a specification decision, not an algorithmic one — ask, then encode it in one visible comparison.

What if intervals arrive as a stream? Unsorted streaming breaks the sealed argument — buffer and sort, or maintain an ordered structure (interval tree / balanced map) at O(log n) per insert. Sorted streaming (timestamps) is the free-lunch case: pure O(1) memory sweep.