DSA & Algorithms
Part 6 of 21 · DSA Interview PatternsSorting, Intervals & Sweep Line — Merge, Overlap & Events
Sort plus sweep for merge intervals, overlaps, and event-based line sweeps.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Order reveals the overlaps
Prefer
Sort, then one left-to-right sweep
After sorting by start, overlap is a local question about the previous end. Events turn the same idea into a counter.
- Merge extends the last end with max, it does not append a new range.
- Meeting rooms is a sweep or a min-heap of end times.
- Touching endpoints are a problem-statement question, not a default.
Alternative
Compare every interval with every other
Quadratic overlap checks throw away the sort.
- Forgetting max on the end.
- Processing a start before an end at the same timestamp when a room should free.
- Reaching for DP when a sweep already answers it.
Sort, then decide against the previous
One pass after the sort. The heap variant is the same story.
- 1
Sort by start
Events sort by time, with ends before starts on a tie. - 2
Compare with the open range
Overlap extends the end. A gap emits the previous range. - 3
Or count active events
Plus one at start, minus one at end. The max is the answer.
Overview
Sort plus sweep for merge intervals, overlaps, and event-based line sweeps.
Below is the full pattern: when to reach for it, a top-down picture, runnable Python and TypeScript templates, complexity, traps, LeetCode drills, and Q&A.
When to use / recognition cues
Use when sorting reveals order, then a linear sweep merges or counts overlaps.
Recognition cues
- merge intervals / insert interval
- meeting rooms / can attend all
- number of overlapping intervals
- skyline / sweep line events
Mental model
Decisions
- 1
Step 1 Sort intervals by start
- nextStep 2 cur = first interval
- skipped the sortFailure path - overlaps that are far apart get missed
- 2
Step 2 cur = first interval
- nextStep 3 Next starts at or before cur end?
- ?
Step 3 Next starts at or before cur end?
- yesStep 4a Merge - cur end = max of both ends
- noStep 4b Emit cur, then cur = next
- 4
Step 4a Merge - cur end = max of both ends
- nextStep 5 Input left?
- 5
Step 4b Emit cur, then cur = next
- nextStep 5 Input left?
- ?
Step 5 Input left?
- yesStep 3 Next starts at or before cur end?
- noStep 6 Emit the last cur
- 7
Step 6 Emit the last cur
- 8
Failure path - overlaps that are far apart get missed
Lesson map
Sorting, Intervals & Sweep Line — Merge, Overlap & Events
Sort plus sweep for merge intervals, overlaps, and event-based line sweeps.
Architecture. Step 1 Sort intervals by start Ready. Step 2 cur = first interval Ready. Step 3 Next starts at or before cur end? Ready. Step 4a Merge - cur end = max of both ends Ready. Step 4b Emit cur, then cur = next Ready. Step 5 Input left? Ready. Step 6 Emit the last cur Ready. Failure path - overlaps that are far apart get missed Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB S["Step 1 Sort intervals by start Ready"] I["Step 2 cur = first interval Ready"] N["Step 3 Next starts at or before cur end? Ready"] M["Step 4a Merge - cur end = max of both ends Ready"] E["Step 4b Emit cur, then cur = next Ready"] D["Step 5 Input left? Ready"] L["Step 6 Emit the last cur Ready"] F["Failure path - overlaps that are far apart get missed Ready"] S -->|continues| I I -->|continues| N N -->|yes| M N -->|no| E M -->|continues| D E -->|continues| D D -->|yes| N D -->|no| L S -->|skipped the sort| F
Read the chart from top to bottom. Two-way decisions keep the card narrow on a phone.
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity analysis
- Sort O(n log n) then sweep O(n).
- Meeting rooms via events: O(n log n).
Common pitfalls & interview traps
LeetCode drill (real problems)
- Merge Intervals
- Insert Interval
- Non-overlapping Intervals
- Meeting Rooms II
- Car Pooling
- The Skyline Problem
Go deeper
- Back to the pattern map.
- NeetCode roadmap
- CP-Algorithms
Interview Q&A
Merge key step?
Answer
Sort by start; extend last end if overlapping.
Meeting rooms II?
Answer
Min heaps on end times, or sweep +/-1 events.
Non-overlapping removal?
Answer
Greedy: keep earliest finishing interval.
Sweep line idea?
Answer
Process start/end events in order; maintain active count.
Touching intervals?
Answer
Clarify if [1,2][2,3] merge - problem-dependent.
Skyline harder piece?
Answer
Multiset of active heights; emit when max height changes.