Unit 2.8 · about 4 h
103 / 324Interval ordering, merging and sweep lines
Intervals turn sorting into scheduling. One sort plus one left-to-right walk answers merging, insertion and concurrency when the running state matches the question's verb.
- implement
You can now
- State the interval-merging invariant and implement
mergeandinsertwith edge tests for touching endpoints and containment. - Implement event sweeps with an explicit tie-break and defend the ends-before-starts versus starts-before-ends choice from the interval convention.
- Solve unseen interval problems by reading the verb (collapse, insert, concurrency) and picking the matching running state.
Covers
- Interval ordering, merging and sweep reasoning
Study, in this order
2 steps
- Merge intervals archetypesDSA Handbook Patterns - merge intervals archetypes
The decision; Variants (Merge overlapping, Insert interval); Three signature problems (LC 56, LC 57); Common misconceptions
Depth · Read the Meeting-rooms-II archetype too; practise it on AlgoMaster below.
- Sweep line archetypesDSA Handbook Patterns - sweep line archetypes
The decision; Variants (1D event sweep); Variants side-by-side
Depth · Read only the 1D event sweep variant; skyline and rectangle area are recognition only.
Focus on
- Sort by start, walk left to right, keep one running merged interval; the overlap test is
s <= last.endunder LC 56's closed intervals. Sorting dominates at \(O(n \log n)\) with \(O(n)\) output. - Insert skips the sort: the input is already sorted and non-overlapping, so one pass splices the before part, the widened overlap and the after part in \(O(n)\). Re-sorting throws the precondition away for an extra \(\log\) factor.
- The sweep tie-break follows the convention: half-open
[s,e)processes ends before starts; closed[s,e]flips it. On[[7,10],[10,11]], ends-first counts 1 (correct for half-open) while starts-first double-counts the boundary. - The verb picks the state: collapse asks for a running interval, a new range asks for a widened
newInterval, concurrency asks for a min-heap of end times or a+1/-1balance counter.
Reproduce closed-book
[[1,3],[2,6],[8,10],[15,18]] must give [[1,6],[8,10],[15,18]], and touching [1,3],[3,5] must merge to [[1,5]]. Insert [2,5] into [[1,3],[6,9]] must give [[1,5],[6,9]]. Implement the +1/-1 event sweep with ends-before-starts; on [[0,30],[5,10],[15,20]] it must report maximum concurrency 2. Differential-test merge against a brute-force pairwise-collapse loop on random interval lists.Traps
- Merging with
<instead of<=on closed intervals. Touching endpoints[1,3],[3,5]overlap under LC 56's convention and must merge. - Using the sweep's \(O(N \log N)\) default as a law. Bounded coordinate ranges admit a difference array at \(O(N + R)\); the sort is the default, not the law.
- Keeping the whole active set when a scalar suffices. Event counting needs one balance counter, not a heap; match the structure to what the question asks at each \(x\).
Practice
Three-phase splice without sorting; example ([[1,3],[6,9]], [2,5]) expects [[1,5],[6,9]]
After submitting, read the AlgoMaster write-up for Insert Interval (https://algomaster.io/learn/dsa/insert-interval).
Read only Understanding the Problem and its Key Constraints, then solve twice: the +1/-1 event sweep with ends before starts, and a min-heap of end times. Test both against a brute-force count at every start time on random meetings, including back-to-back [7, 10], [10, 11].
After both pass, read Approaches 2 and 3 (min-heap, and two sorted arrays) and compare their tie rules with yours.
Sort by start plus running merge; example [[1,3],[2,6],[8,10],[15,18]] expects [[1,6],[8,10],[15,18]]
Use only if interval modeling is still weak after the pattern pages; state the overlap convention before coding. After submitting, read the AlgoMaster write-up for Merge Intervals (https://algomaster.io/learn/dsa/merge-intervals). Transfer check: solve one unseen heap-or-interval problem on NeetCode (for example LC 435 Non-overlapping Intervals, https://leetcode.com/problems/non-overlapping-intervals/) with solutions closed.
Self-test
-
Prove the merge walk never splits two overlapping intervals.
Sorted by start, the walk keeps the running interval with the maximum end so far. Any interval with start <= running end overlaps it and widens it further; an interval with start > running end overlaps nothing later either, since later starts are even larger. Each emission is therefore maximal. -
Why is insert \(O(n)\) while merge is \(O(n \log n)\)?
Insert's input is sorted and non-overlapping, so one linear splice (before, widened overlap, after) suffices. Merge must establish the order first, and comparison sorting costs \(O(n \log n)\). -
Under the half-open convention, why do ends sort before starts at equal coordinates?
At \(x=10\),[7,10)has already ended while[10,11)begins; processing the-1first keeps the count at 1. Starts-first would briefly count 2 and double-count the shared boundary. -
What changes if intervals arrive as an unbounded stream?
If meetings arrive in start order, a min-heap of active end times (pop while top <= start) processes them online in \(O(n \log n)\) time with \(O(n)\) state. If they arrive in arbitrary order, no single pass works: keep an ordered map of+1/-1events, or a segment tree over bounded coordinates, and update the maximum as events land.
Completion criterion
Stop when
Merge and insert match the handbook examples, the sweep reports concurrency 2 on the worked input, merge survives a brute-force differential test, and you route a new interval task from its verb.
Mark passed, then open 3.1 Only mark this when you can do it without notes.Leads to
- 4.4 Greedy counterexamples and interval scheduling Interval scheduling proofs build on the merging order established here.
- 2.6 Heaps and priority queues Concurrency counting reuses the heap as its active set.
Comes after
- 2.3 Binary search: intervals, bounds and feasibility predicatesSorted order plus boundary discipline returns in interval merging.
- 4.4 Greedy counterexamples and interval schedulingMerging, sweep lines, and room-booking variants that need more than earliest-finish.
Resources for this unit
- DSA Handbook Patterns - merge intervals archetypes Use The decision, Variants and the LC 56 and LC 57 signature problems for merge and insert implementation, and the Meeting Rooms II archetype for the min-heap form.
- DSA Handbook Patterns - sweep line archetypes Use The decision and the 1D event sweep variant for
+1/-1concurrency counting with explicit tie-breaks; skyline and rectangle area are recognition only.
Also in this section
- DSA Handbook - search, trees and heaps Study Part 2 Search and Sort, Part 5 Linked Lists, and Part 6 Trees and Heaps. Include canonical and answer-space binary search, comparison and linear-time sorts, quickselect, sentinels, cycles, heaps, BSTs, balanced-tree vocabulary, tries and segment trees.
- AlgoMaster DSA - ordered structures slice Attempt Koko Eating Bananas, Validate Binary Search Tree and Find Median from Data Stream cold. Use Merge Intervals only if interval modeling remains weak, and include duplicate-heavy and skewed inputs.
- Algorithmica - search and sorting performance Use the binary-search, sorting, branch prediction and cache chapters to explain why two algorithms with the same asymptotic bound cross over on real workloads.
- Algorithms Use Chapter 1 (mergesort, quicksort, recursion trees and linear-time selection) when deriving merge, partition and selection algorithms, and lecture note 12 Lower Bounds for the comparison-sorting decision-tree argument. This is the proof reference when the handbook explanation is too brief.
- NeetCode - unseen ordered problems Use one unseen tree problem and one heap or interval problem as the final transfer check, with solution material closed until submission.
- DSA Handbook Patterns - quicksort vs mergesort vs heapsort Use The decision, Algorithms compared and Side-by-side to pick a comparison sort from the binding constraint; problem details stay with their units.
- DSA Handbook Patterns - quickselect vs heap for top-K Use The decision through Side-by-side for the streaming, sorted-output and mutation routing; problem details stay with their units.
- DSA Handbook Patterns - two-heap median archetypes Use Streaming median and Variants side-by-side for the two-heap invariants; skip sliding-window median and sketches.