Problem #452: Minimum Number of Arrows to Burst Balloons

Intuition & Strategy Breakdown

Sort balloons by end coordinate. Greedily shoot arrow at end coordinate of first balloon, bursting all overlapping balloons.

Python Solution

class Solution:
    def findMinArrowShots(self, points: list[list[int]]) -> int:
        points.sort(key=lambda x: x[1])
        arrows = 1
        end = points[0][1]
        for p in points[1:]:
            if p[0] > end:
                arrows += 1
                end = p[1]
        return arrows

Java Solution

class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0) return 0;
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
        int arrows = 1;
        int end = points[0][1];
        for (int i = 1; i < points.length; i++) {
            if (points[i][0] > end) {
                arrows++;
                end = points[i][1];
            }
        }
        return arrows;
    }
}