Balloons are intervals on the x-axis. An arrow shot at x bursts every balloon with start ≤ x ≤ end. Return the minimum number of arrows.
Before you code
The balloon that ends first must be hit by some arrow at or before its end. Shooting exactly at its end hits it and as many others as possible.
Hints
- Sort by end.
- Shoot at the first balloon's end; skip every balloon whose start is at most that point.
- Shoot again at the next unburst balloon's end. Note that touching counts here: closed intervals.
Production & complexity notes
When solving Minimum number of arrows to burst balloons on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Scheduling and intervals to reinforce the underlying pattern.
What it practices
The earliest-end rule in another form, from Scheduling and intervals.