Minimum Number of Arrows to Burst Balloons
Balloons are given as horizontal intervals. An arrow shot upward at x bursts every balloon whose interval contains x. Return the minimum number of arrows needed.
Open on LeetCode ↗Intuition
This is Non-overlapping Intervals wearing a different costume, and it carries one extra trap worth naming up front: balloons that touch at a single coordinate. [1,2] and [2,3] are burst by one arrow at x = 2, so a strict comparison counts an arrow that was never needed. Past that, the shape is familiar — sort by end coordinate and shoot at the end of the first balloon still intact, the position that hits the most at once. The answer is the number of groups you cannot merge.
Approach
Sort by the end coordinate
Sorting by start fails for the same reason it fails in activity selection: one wide balloon can dominate several narrow ones. Sorting by end works because if you must shoot the earliest-ending balloon at all, shooting at its right edge is optimal — every other balloon that edge reaches would also be reached by any earlier shot, and none is lost.
Shoot at the current end and sweep
Take the first balloon's end as the arrow position and count one arrow. Walk the rest: if a balloon's start is at or before that position, the arrow already bursts it, so skip it. Otherwise it is out of range — fire a new arrow and move the position to this balloon's end.
Watch the touching case and the overflow
Balloons touching at a single point, like [1,2] and [2,3], are burst by one arrow at x = 2, so the comparison must be start <= pos, not strict. Using < counts an extra arrow. Also, LeetCode's coordinates reach the 32-bit limits, so comparing start > pos directly is safer than computing a difference that could overflow in a fixed-width language. O(n log n) for the sort, O(1) beyond it.
Solution & live demo
Edge cases
One arrow suffices.
One arrow bursts them all.
Still burst by a single arrow — the <= comparison is what gets this right.
Each needs its own arrow, so the answer equals the count.