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.
Interval scheduling again: sort by end coordinate and fire an arrow at the end of the first balloon, which pops every balloon overlapping it. Choosing the earliest possible end maximises what a single arrow covers — the same exchange argument as Non-overlapping Intervals.
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
Common pitfalls
Sorting by start coordinate
points.sort(key=lambda x: x[0])
points.sort(key=lambda x: x[1])
Firing at a balloon's start can miss later balloons that a slightly further shot would catch. Anchoring at the earliest end guarantees the arrow is as far right as it can be while still bursting the current balloon.
Using >= for the new-arrow test
if s >= pos:
if s > pos:
A balloon starting exactly where the arrow was fired is still touched by it — the ranges are inclusive. The strict test correctly reuses the arrow; >= fires an unnecessary extra one.
Sorting with subtraction on large coordinates
sort(points.begin(), points.end(), [](auto&a, auto&b){ return a[1] - b[1] < 0; });return a[1] < b[1];
Coordinates reach ±2^31, so a[1] - b[1] overflows a 32-bit int and produces an inconsistent comparator — which can corrupt the sort or crash. Compare directly instead of subtracting.
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.