Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Measure peak simultaneous demand: The Hall Allocation.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Meeting-room sweep line matches the clues
- 2Keep this true after every move: active equals meetings started but not yet ended at the current event
- 3Reach the result within O(n log n)
Rules and pressure
- Target cost: O(n log n)
- State rule: active equals meetings started but not yet ended at the current event
Lesson 1 of 3
Live algorithm trace
Meeting-room sweep line
Complete execution1 of 6
Separate and sort all start and end events.
1
starts = sorted starts; ends = sorted ends2
if next start < next end3
active += 1; advance start4
otherwise active -= 1; advance end5
best = max(best, active)6
return beststarts = [0,5,15]ends = [10,20,30]active = 0
Truth to preserve / Cost target
Truth to preserve
active equals meetings started but not yet ended at the current event
Cost target
O(n log n)
Sort starts and ends separately. The next event either opens a room or frees one; the maximum number of active meetings is the minimum number of rooms required.
Your call · What should guide every step of this algorithm?