Minimum Number of Arrows to Burst Balloons

Problem in plain words

Each balloon covers a horizontal range [xStart, xEnd]. An arrow shot straight up at position x bursts every balloon whose range contains x, including balloons whose edge is exactly x. Find the fewest arrows that burst every balloon.

For example, balloons [1, 2], [2, 5] and [6, 7] need 2 arrows: one at x = 2 bursts the first two, one at x = 6 bursts the last.

Intuition

Look at the balloon that ends first. Some arrow must hit it, and the best place for that arrow is its right edge: moving the shot further left can only miss balloons that start later, while any point further right misses this balloon entirely. Every balloon that starts at or before that edge is popped by the same arrow. Then repeat with the first balloon left standing. This is the same earliest-finish greedy as activity selection; the number of arrows equals the number of non-overlapping groups.

Approach

1. Sort balloons by their end coordinate.
2. Shoot the first arrow at the end of the first balloon: arrows = 1, arrowX = points[0][1].
3. For each next balloon, if its start is at most arrowX, the current arrow already bursts it.
4. Otherwise shoot a new arrow at this balloon's end: arrows++, arrowX = end.
5. Return arrows.

Dry run

Input: [[3, 7], [1, 4], [8, 10], [5, 9]]. Sorted by end: [1, 4], [3, 7], [5, 9], [8, 10].

Java solution

class Solution {
    public int findMinArrowShots(int[][] points) {
        // Integer.compare avoids overflow: coordinates span the full int range.
        Arrays.sort(points, (x, y) -> Integer.compare(x[1], y[1]));
        int arrows = 1;
        int arrowX = points[0][1];
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > arrowX) {   // this balloon starts after the arrow
                arrows++;
                arrowX = points[i][1];
            }
        }
        return arrows;
    }
}

Python solution

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort(key=lambda p: p[1])
        arrows = 1
        arrow_x = points[0][1]
        for start, end in points[1:]:
            if start > arrow_x:   # this balloon starts after the arrow
                arrows += 1
                arrow_x = end
        return arrows

Complexity

Edge cases and common mistakes

• Comparator overflow: coordinates range from -2^31 to 2^31 - 1, so a[1] - b[1] overflows and sorts wrongly. This is the most common failed test on this problem.
• Touching balloons: [1, 2] and [2, 3] share one arrow, so the new-arrow test must be strictly start > arrowX.
• Nested balloons: a small balloon inside a big one is handled correctly because sorting by end shoots at the small one's edge, which lies inside the big one.
• Single balloon: the answer is 1.