Merge Intervals vs Sweep Line
Use the merge pass when the answer is itself a set of intervals. Use a sweep line when the answer is a number about overlap at a moment, such as how many events run at once or when the busiest point is.
Both start by sorting, and they sort different things. Merging sorts the intervals by start and walks them, carrying one open interval it either extends or closes. A sweep line throws the intervals away and keeps only their endpoints as events, plus one at each start and minus one at each end, then walks those in time order while a counter rises and falls.
Side by side
| Dimension | Merge intervals | Sweep line |
|---|---|---|
| Output | A list of intervals | A count, a maximum, or the moment it occurs |
| Sorted by | Start time | Event time, with ends before starts on ties |
| State carried | One current interval | One running counter |
| Cost | O(n log n) for the sort, O(n) for the pass | O(n log n) for the sort, O(n) for the pass |
| Maximum overlap | Not directly available | The peak of the counter |
| Rooms or resources needed | Not directly available | Exactly the peak counter |
When to pick each
Merge intervals
- Merge overlapping intervals, insert an interval into a sorted list, or report the free gaps between bookings.
- Anything whose answer is a calendar you could draw: the union of busy periods, the compressed set of ranges.
Sweep line
- Meeting rooms: the minimum number of rooms is the largest number of meetings open at once.
- Finding the busiest minute, or the first moment a limit is exceeded.
- Counting how many intervals cover each point, where the running counter is the answer per step.
Getting the tie-break wrong in the sweep. A meeting that ends at 10 and another that starts at 10 do not overlap, so the end event has to be processed first, and sorting the events naively can put the start first and report one room too many. In the merge pass the matching slip is sorting by end time instead of start, which quietly merges intervals that do not touch.
Questions people ask
Is the two-heap meeting rooms solution different?
It is the same idea with different bookkeeping. Sorting starts and keeping a min-heap of end times tracks exactly the set of currently open meetings, and the heap size is the counter a sweep line keeps directly. The sweep is usually simpler to write and explain, and both are O(n log n).
When do I need an interval tree instead?
When the intervals keep changing or you have to answer many which intervals cover this point queries. A sweep is a single pass over a fixed set, so repeated queries mean repeated passes. An interval tree or a segment tree pays O(n log n) once and then answers each query in O(log n).
Why does almost every interval problem start with a sort?
Because overlap is a local property once the intervals are in order. Unsorted, deciding whether two intervals overlap means comparing every pair, which is O(n squared). Sorted by start, an interval can only overlap the one you are currently holding, which is what turns the whole family into a single linear pass.