Run it
The sweep with each decision printed, the contained-interval case that breaks the naive extend, and both answers to the touching question.
The solution
O(n log n) time — dominated by the sort — and O(n) space for the output, or O(1) extra if merging in place is allowed.
Two details carry the correctness:
start <= last_end treats touching intervals as overlapping, so [1,3] and [3,5] merge into [1,5]. If touching should stay separate, use <. Ask which is wanted — it is a genuine ambiguity and interviewers use it.
max(last_end, end) is necessary because the new interval may be entirely contained in the previous one. Assigning end directly would shrink [1,10] to [1,3] when merging [2,3] into it — a bug that only appears on nested intervals.
Why sorting is what makes it work
Without sorting, an interval can overlap any other, so every pair must be checked and merges cascade — O(n²) at best, with awkward bookkeeping.
Sorted by start, the invariant is: the output list's last interval is the only one the next input interval can extend. Everything earlier in the output ends before the current interval begins, because starts are non-decreasing and the output's earlier entries were finalised.
That invariant is the argument for correctness, and stating it is worth more in an interview than the code — it explains why one comparison per interval suffices.
Note what sorting by end instead would give: that is the activity-selection greedy criterion for choosing the maximum number of non-overlapping intervals, a different problem with a different rule. Which field you sort by encodes which question you are answering.
Why sorting collapses the problem
Unsorted, any interval can overlap any other, so you are looking at pairs — O(n²). Sorted by start, an interval's only possible overlap is with the merged block immediately behind it, because everything earlier starts earlier and has already been absorbed.
That reduces the whole thing to one comparison per interval. The sort costs O(n log n) and dominates.
The line people get wrong
When extending, take max(last_end, this_end), not this_end. A fully contained interval — [1, 10] then [2, 3] — would otherwise shrink the merged block to 3 and silently lose everything from 3 to 10.
The other decision is whether touching counts as overlapping. [1, 3] and [3, 5] merge under lo <= last_end and stay separate under <. Both are defensible; ask which the question wants.
What it generalises to
Meeting rooms, calendar conflicts, genome ranges, IP blocks — all the same sweep. The variants change only the merge rule: count how many rooms are needed simultaneously (a sweep line with +1 and −1 events), insert one interval into an already-merged list, or find the gaps rather than the blocks.
Edge cases
| Case | Input | Result |
|---|
| Empty | [] | [] |
| Single interval | [[1,3]] | [[1,3]] |
| Fully nested | [[1,10],[2,3]] | [[1,10]] — needs the max |
| Touching | [[1,3],[3,5]] | [[1,5]] or two, depending on the convention |
| Identical | [[1,3],[1,3]] | [[1,3]] |
| Already sorted | Any | The sort is still O(n log n) |
| Reverse sorted | Any | Sorting handles it |
| Zero-length interval | [[2,2]] | Valid point interval; confirm it is allowed |
The nested case is the one that breaks naive implementations, and it is worth constructing deliberately when testing: [[1,10],[2,3],[4,5]] must give [[1,10]].
The interval-problem family
Once the sort-then-sweep shape is recognised, a whole family follows:
Insert an interval into a sorted list. Three phases: intervals ending before the new one, intervals overlapping it (merge them all), and intervals starting after. O(n) without re-sorting.
Does any pair overlap? Sort by start and check consecutive pairs — O(n log n), and it is what a meeting-room double-booking check does.
Minimum meeting rooms. The number of concurrently active intervals at the busiest moment. Two standard approaches: a min-heap of end times, or separating starts and ends into events and sweeping.
Erase overlapping intervals. Sort by end and greedily keep non-overlapping ones — the activity-selection problem, and the reason sorting by end matters.
Interval intersection of two sorted lists. Two pointers, advancing whichever interval ends first.
Employee free time. Merge all busy intervals, then take the gaps.
The sweep line technique
For the "how many are active at once" questions, the general tool is a sweep line: convert each interval into two events and process them in time order.
The sort order at ties matters: (t, -1) sorts before (t, 1) because −1 < 1, so an interval ending at time t frees its slot before one starting at t claims it. That is the touching convention again, and choosing the other convention means adjusting the tie-break.
Sweep line generalises well: it handles maximum overlap, total covered length, and the same questions in two dimensions (rectangle area, skyline problems).
What it is testing
Do you sort first? The whole problem hinges on it, and volunteering it immediately is the expected opening.
Do you handle the nested case? max(last_end, end) rather than assignment.
Do you ask about touching intervals? A real ambiguity in the specification.
Do you state the complexity correctly? O(n log n) from the sort, not O(n).
Do you recognise the family? Meeting rooms, insert interval and activity selection are all follow-ups, and knowing which field to sort by distinguishes them.
Recap in one screen
- Sort by start; then each interval can only extend the last one in the output.
- Merge when
start <= last_end, and take max of the ends to handle nested intervals. - O(n log n) from the sort, O(n) output.
- Ask whether touching intervals count as overlapping — it changes the comparison.
- Sort by end instead for activity selection, and use a sweep line for concurrency questions.