Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Reject any overlapping meeting: The Single Hall.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Meeting conflict detection matches the clues
- 2Keep this true after every move: all meetings before the scan index are mutually compatible
- 3Reach the result within O(n log n)
Rules and pressure
- Target cost: O(n log n)
- State rule: all meetings before the scan index are mutually compatible
Lesson 1 of 3
Live algorithm trace
Meeting conflict detection
Complete execution1 of 4
Sort all meetings by their start time.
1
sort meetings by start2
for each adjacent pair3
if current start < previous end: return false4
return trueorder = already sorted
Truth to preserve / Cost target
Truth to preserve
all meetings before the scan index are mutually compatible
Cost target
O(n log n)
After sorting meetings by start, an overlap can only occur with the immediately previous meeting. If every start is at least the previous end, one room is enough.
Your call · What should guide every step of this algorithm?