Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Merge connected spans: Bridge the Overlaps.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Interval merging matches the clues
- 2Keep this true after every move: merged intervals are sorted and nonoverlapping
- 3Reach the result within O(n log n)
Rules and pressure
- Target cost: O(n log n)
- State rule: merged intervals are sorted and nonoverlapping
Lesson 1 of 3
Live algorithm trace
Interval merging
Complete execution1 of 5
Sort intervals by start. This input is already in start order.
1
intervals.sort()2
compare next start with last end3
merge or append4
return mergedmerged = []
Truth to preserve / Cost target
Truth to preserve
merged intervals are sorted and nonoverlapping
Cost target
O(n log n)
After sorting intervals by start time, only the most recently merged interval can overlap the next one. Extend it or begin a new span.
Your call · What should guide every step of this algorithm?