Minimum Number of Arrows to Burst Balloons

Problem Statement

You’re an archer with balloons floating on a 2D plane, each defined by [x, yStart, x, yEnd]. Find the minimum arrows needed to burst all balloons, where an arrow at x bursts all balloons overlapping that x-coordinate. This medium-level greedy problem is about precision—hit as many balloons as possible with each shot!

Example

Input: points = [[10,16],[2,8],[1,6],[7,12]]

Output: 2 (arrows at x=6 and x=12)

Input: points = [[1,2],[3,4],[5,6],[7,8]]

Output: 4 (no overlaps, one arrow per balloon)

Code

public 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;
    }
}
            

def find_min_arrow_shots(points):
    if not points:
        return 0
    points.sort(key=lambda x: x[1])
    arrows = 1
    end = points[0][1]
    for i in range(1, len(points)):
        if points[i][0] > end:
            arrows += 1
            end = points[i][1]
    return arrows
            

function findMinArrowShots(points) {
    if (!points.length) return 0;
    points.sort((a, b) => a[1] - b[1]);
    let arrows = 1;
    let end = points[0][1];
    for (let i = 1; i < points.length; i++) {
        if (points[i][0] > end) {
            arrows++;
            end = points[i][1];
        }
    }
    return arrows;
}
            

Explanation

• Greedy Choice: Sort by end coordinates, shoot at the earliest end to burst overlapping balloons.
• Flow: If a balloon starts after the current end, use a new arrow.
• Example: [[1,6],[2,8],[7,12],[10,16]] → shoot at 6 (bursts 1,2), then 12 (bursts 3,4).

Note