DSA & Algorithms
Part 5 of 16 · DSA Advanced & Company FavoritesIntervals Advanced - Meeting Rooms, Merge, Sweep Priorities
Meeting rooms, merge intervals, employee free time, and sweep-line priority queues.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Ranges start, end, and overlap
Prefer
Sort, then sweep
A heap of end times answers meeting rooms. A scan merges overlaps.
- Process an end before a start at the same timestamp.
- The active count is the room count.
- One sweep can also add capacity, as in car pooling.
Alternative
Compare every pair
Quadratic overlap checks miss the sweep structure.
- You sort by end when the merge key is start.
- You double-count a touching boundary.
- You allocate a room per meeting.
Sweep a timeline
Ends before starts at the same timestamp.
- 1
Emit events
Start adds one. End subtracts one. - 2
Sort the events
Time, then end before start. - 3
Track the active count
The maximum is the room count.
Overview
Meeting rooms, merge intervals, employee free time, and sweep-line priority queues.
When companies ask this
Recognition cues: meeting rooms / II; merge intervals; insert interval; employee free time; car pooling; min arrows.
Deepens wave-1 dsa-sorting-intervals with rooms + heap sweep.
Mental model
Flow
- 1
1. Emit start and end events
- next2. Sort time, end before start
- 2
2. Sort time, end before start
- next3. Sweep the active count
- 3
3. Sweep the active count
- next4. Heap of ends when you need rooms
- 4
4. Heap of ends when you need rooms
Lesson map
Intervals Advanced - Meeting Rooms, Merge, Sweep Priorities
Meeting rooms, merge intervals, employee free time, and sweep-line priority queues.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB events["1. Emit start and end events"] sort["2. Sort time, end before start"] sweep["3. Sweep the active count"] heap["4. Heap of ends when you need rooms"] events -->|1. Emit start and end events| sort sort -->|2. Sort time, end before start| sweep sweep -->|3. Sweep the active count| heap
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 + pitfalls
- Merge O(n log n); rooms O(n log n) heap.
- Pitfalls: inclusive/exclusive ends; sort start==end order; mutating while iterating.
Interviewer traps
LeetCode drill (real problems)
- Merge Intervals
- Insert Interval
- Meeting Rooms
- Meeting Rooms II
- Non-overlapping Intervals
- Minimum Number of Arrows to Burst Balloons
- Car Pooling
- The Number of the Smallest Unoccupied Chair
- Remove Covered Intervals
YouTube
Interview Q&A
Merge key?
Answer
Sort by start; extend if overlap.
Rooms II?
Answer
Min heap of end times; pop if free before next start.
Max concurrent via sweep?
Answer
+1 start -1 end; track max active.
Insert interval?
Answer
Add non-overlapping left, merge middle, append right.
Employee free time?
Answer
Merge all busy; gaps between merges.
Open vs closed?
Answer
Clarify; often [start,end) for rooms.
Related wave-1?
Answer
sorting-intervals, heaps, greedy.
Car pooling?
Answer
Diff array or sweep passengers.