Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Cover maximum spans with minimum points: The Balloon Line.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when Greedy interval stabbing matches the clues
- 2Keep this true after every move: the latest arrow sits at the earliest end among all balloons it covers
- 3Reach the result within O(n log n)
Rules and pressure
- Target cost: O(n log n)
- State rule: the latest arrow sits at the earliest end among all balloons it covers
Lesson 1 of 3
Live algorithm trace
Greedy interval stabbing
Complete execution1 of 6
Sort balloons by their right endpoints.
1
sort balloons by end2
arrows = 03
if start > lastArrow4
shoot at current end5
return arrowsarrows = 0lastArrow = none
Truth to preserve / Cost target
Truth to preserve
the latest arrow sits at the earliest end among all balloons it covers
Cost target
O(n log n)
Sort balloons by their right endpoint. Shoot at the earliest end; that point bursts every overlapping balloon while preserving the greatest possible reach into future intervals.
Your call · What should guide every step of this algorithm?