Minimum Number of Arrows to Burst Balloons
Picture balloons taped to a wall, each drawn as a horizontal bar. Balloon i is given by points[i] = [start, end] — the left and right x-coordinates it covers. Balloons may overlap.
You shoot arrows straight up from the x-axis. An arrow fired at position x rises forever and bursts every balloon whose bar crosses that vertical line, that is, every balloon with start <= x <= end. So one well-aimed arrow can pop several overlapping balloons at once.
Drag the arrow above to see which balloons a single shot bursts. Return the minimum number of arrows needed to burst all the balloons.
Input & Output
Input
points — each points[i] = [start, end] is the horizontal span of one balloon
Output
the minimum number of arrows needed to burst every balloon
Example
Input
points = 4 10 16 2 8 1 6 7 12
Output
2
Explanation
Two arrows suffice. One arrow at x = 6 bursts [1,6] and [2,8]; another at x = 12 bursts [7,12] and [10,16].
Example
Input
points = 3 1 5 2 6 3 7
Output
1
Explanation
All three balloons overlap at x = 3 (and x = 4), so a single arrow there bursts all of them.