Intermediate · Module 15 · Lesson 5
Meeting rooms
Count simultaneous intervals with heaps or events.
15–25 min readLesson 87 of 123
Lesson 87 of 123
1d streakTheory lesson · Step-by-step
Understand Meeting rooms
Count simultaneous intervals with heaps or events.
Worked approach
Trace the reasoning step by step
- 1Sort starts and ends or sort meetings by start.
- 2Release rooms whose meetings ended.
- 3Allocate a room for the next start.
- 4Track the maximum simultaneous count.
Concrete example
Find rooms for meetings [0,30], [5,10], [15,20].
- 1At time 5, two meetings overlap.
- 2At time 15, the [5,10] room is reusable.
Maximum concurrency is 2 rooms.
What must remain true (Loop Invariant)
The active structure contains exactly the meetings that have started but not ended.
Cost Model
Complexity & Trade-offs
OperationTimeSpaceWhy
Sort and scan
O(n log n)
O(n)
Sorting establishes the order that makes one linear scan possible.When to use it
- Autocomplete, dictionary prefixes, wildcard matching, overlap, and scheduling.
- Sharing common string prefixes.
- Reducing range problems to ordered start/end events.
Common mistakes
- Forgetting terminal markers in a trie.
- Treating touching intervals as overlap without checking the problem convention.
- Processing equal-time events in the wrong order.
Practice prompts
- Reproduce the worked Meeting rooms example without looking at the trace.
- Change one input condition and explain whether the Meeting rooms invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check
Can you derive it instead of memorizing it?
State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.