DSA problem
Minimum Number of Arrows to Burst Balloons
There are some spherical balloons taped onto a flat wall that represents the xy-plane. The balloons are represented as a 2D integer array points where points[i] = [x_start, x_end] denotes a balloon whose horizontal diameter stretches between x_start and x_end. Arrows are shot up directly vertically from the x-axis at a given location x. A balloon with x_start <= x <= x_end bursts. Return the minimum number of arrows that must be shot to burst all balloons.
The problem is equivalent to covering a set of closed intervals on the x-axis with the smallest possible number of points such that every interval contains at least one chosen point. This is a classical greedy interval covering problem.
The greedy insight is that, after sorting balloons by their right endpoint, you should always shoot your next arrow at the rightmost end of the leftmost balloon that is not yet burst. Any earlier position would still burst that balloon but cover fewer of the balloons coming after it; any later position would miss that leftmost balloon entirely. The chosen position therefore bursts the maximum number of overlapping balloons.
Algorithmically, sort by end. Initialize the arrow position to points[0][1]. For each subsequent balloon, if its start is greater than the current arrow position, the arrow cannot reach it: increment the arrow count and reposition the arrow to the new balloon's right end. Otherwise the existing arrow still bursts it. This runs in O(n log n) time and O(1) extra space beyond the sort.
Examples
points = [[10,16],[2,8],[1,6],[7,12]]2points = [[1,2],[3,4],[5,6],[7,8]]4points = [[1,2],[2,3],[3,4],[4,5]]2Constraints
- 1 <= points.length <= 10^5
- points[i].length == 2
- -2^31 <= x_start < x_end <= 2^31 - 1
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.