Why must overlapping intervals be sorted by start before a single-pass merge?
answer
- what does the sort actually buy the loop
- the pass holds only one open interval
- can a later interval reach back?
- arrival order gives no such promise
- a gap in sorted order is final
basics
~20 sSorting by start guarantees any interval that could overlap the one being built arrives before the pass moves past it. In arrival order, an overlapping slot can appear after you already emitted an interval, so a single pass misses merges.
solid answer
~50 sThe single-pass merge keeps exactly **one** interval open — the last one written to the output — and compares each incoming interval only against that one. That is only sound if nothing later can reach back into an interval you already closed. Sorting by start ascending gives you exactly that guarantee: once you meet an interval whose start is past the open interval's end, every remaining interval starts at least as late, so none of them can touch it either, and closing it is final. Feed the same loop a busy-slot list in arrival order — say three synced calendars concatenated — and a 09:00 slot can show up after you closed an 11:00 one, so overlapping ranges survive into the output. The sort costs `O(n log n)` and dominates the `O(n)` scan; if the source already emits ranges in start order, you can skip it.
go deeper
Be ready to say in one breath that the pass keeps only one interval open, and that sorting by start is what makes closing an interval safe. Name the symptom of skipping it: overlapping ranges left in the output.
Explain the invariant explicitly — after a gap appears in start order, no remaining interval can reach the closed one — and give the cost split: an O(n log n) sort dominating an O(n) scan.
Show the production instinct: the sortedness is an unchecked precondition on data coming from several producers. Say how you would assert it, and what shuffled-input property test you would demand in review.
Own the contract question: is start-ordering a guarantee the producing service owes, enforced at the boundary, or a defensive sort every consumer pays for? Argue the choice on latency, data volume and how many teams touch the feed.
## What the single pass actually does The merge routine walks the input once and maintains a single piece of mutable state: the *open* interval, which is the last interval appended to the output. For each incoming interval it asks one question — does this start at or before the open interval's end? If yes, the two belong to the same merged run and the open interval's end is stretched. If no, the open interval is finished forever and the incoming one becomes the new open interval. That design is what makes the pass `O(n)` in time and `O(1)` in working state beyond the output. But it buys that cheapness with a strong assumption: **an interval, once closed, can never be reopened.** ## The guarantee sorting provides Sorting ascending by start gives the loop the invariant it needs. Suppose the open interval currently covers `[s, e]` and the incoming interval starts at `t` with `t > e`. Because the input is sorted by start, every interval *after* this one also starts at `t` or later, hence also after `e`. None of them can overlap `[s, e]`. Closing it is therefore permanent and correct. Stated as an invariant: *after processing the first `i` intervals of the sorted input, the output holds the correct merge of exactly those `i` intervals, and only the last output interval can still grow.* The sort is what makes the second half of that sentence true. Note what sorting does **not** give you. It does not remove overlaps — that is the merge's job. It does not make the ends monotone either: `[9:00, 17:00]` legitimately precedes `[10:00, 10:30]` in start order. And it does not reduce the pairwise-overlap question to neighbours in general; it only guarantees that *reachability* is exhausted the moment a gap appears. ## What unsorted input looks like in practice Consider a calendar service that builds a free/busy strip by concatenating busy slots pulled from three synced sources. The concatenated list is grouped by source, not by time. Feed it straight into the merge loop: - source A yields `[09:00, 10:00]`, `[13:00, 14:00]` - source B yields `[09:30, 11:00]` Processing in arrival order: `[09:00, 10:00]` opens, `[13:00, 14:00]` does not touch it so `[09:00, 10:00]` closes and `[13:00, 14:00]` opens. Then `[09:30, 11:00]` arrives; it does not touch the open `[13:00, 14:00]`, so it is appended as a third interval. The output is `[09:00, 10:00]`, `[13:00, 14:00]`, `[09:30, 11:00]` — still overlapping, and no longer even in time order. The free/busy strip renders a slot as both busy and free depending on which entry a renderer reads first. The cruel part is that this bug hides. Most hand-written fixtures are typed in chronological order because that is how humans write examples, so every test passes. The defect only appears once a real multi-source feed hands you the intervals grouped some other way. When you review this code, the test to demand is one whose input is deliberately shuffled — and the assertion should be that the output intervals are disjoint and ordered, not merely that the count matches. ## Cost accounting The scan is `O(n)` time. The sort is `O(n log n)` comparisons, so the total is `O(n log n)` and the sort dominates. Space is `O(n)` for the output plus whatever the sort needs. Two consequences follow: 1. If the upstream source already emits ranges ordered by start — a time-ordered event log, a range query against an ordered store — you can drop the sort and the whole operation is linear. Assert the precondition rather than assuming it silently. 2. If you are merging repeatedly into an already-merged structure, re-sorting the whole list every time is the wasteful choice; a merged list is already sorted and disjoint, and a new range can be spliced into it in one linear pass. ## Sorting by something else Sorting by end ascending is a different tool with a different purpose and does not support this pass — with ends sorted, a later interval can easily start before the open interval's start, and the one-open-interval invariant collapses. For merging, start order is the right key. Tie-breaking among equal starts does not matter for correctness of the merge: two intervals with the same start always overlap, so they merge in either order.
- The input is already sorted by start. What is the total cost then, and what would you do about the assumption?The merge itself is `O(n)` time and `O(n)` output space, so the whole operation is linear once the sort is skipped. But an unchecked precondition is a landmine: either assert it cheaply while scanning (each start is at least the previous one — free, since you are already walking the list) and fail loudly, or make the sorted order part of the type/contract the producer must satisfy. Silently trusting it is how the shuffled-feed bug ships.
- Could you get a correct merge without sorting at all?Yes, but not in one cheap pass. You could compare every interval against every other and union transitively, which is `O(n^2)`, or bucket by a coarse time key and merge within buckets, which needs care at bucket edges. Both are more code and more cost than one `O(n log n)` sort followed by a linear scan. Sorting is the cheapest way to make locality — overlapping intervals become adjacent — do the work for you.
- How would you test that a merge routine really tolerates arbitrary input order?Randomly shuffle the input before each run and assert properties rather than an exact list: the output intervals are strictly ordered and pairwise disjoint, total covered length is preserved, and every input interval is contained in some output interval. Property assertions on a shuffled input catch the arrival-order bug that a hand-typed chronological fixture never will.
It is like handling arriving guests strictly by arrival time: once the clock is past a table's booking window, nobody still in the queue can claim that table. Shuffle the queue and you hand out the same table twice.
saying these in an interview costs you the question
- Says sorting is only for tidy output, not correctness
- Thinks unsorted input just makes the merge slower
- Believes sorting by start also orders the ends
- Claims sorting removes overlaps by itself
- Assumes an interval can be reopened later in the pass