Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Remove the fewest conflicting requests: The Quiet Calendar.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Earliest-finish interval scheduling matches the clues
- 2Keep this true after every move: kept intervals are compatible and have the earliest possible final end for their count
- 3Reach the result within O(n log n)
Rules and pressure
- Target cost: O(n log n)
- State rule: kept intervals are compatible and have the earliest possible final end for their count
Lesson 1 of 3
Live algorithm trace
Earliest-finish interval scheduling
Complete execution1 of 6
Sort by end time, placing 1-2 first.
1
sort intervals by end2
lastEnd = negative infinity3
keep if start >= lastEnd4
otherwise remove5
return removal countorder = by endremoved = 0
Truth to preserve / Cost target
Truth to preserve
kept intervals are compatible and have the earliest possible final end for their count
Cost target
O(n log n)
Sort by finishing time and keep every interval whose start reaches the last kept end. Earliest finish leaves at least as much room for all future choices as any alternative.
Your call · What should guide every step of this algorithm?