Minimum ARrows to Burst All Ballons #452

452.Minimum Arrows to Burst Balloons

Interval

Greedy

Sorting

Problem Statement:

There are some spherical balloons spread in 2D space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. An arrow can be shot up directly from different points along the x-axis. A balloon with x_start and x_end is burst by an arrow shot at x if x_start ≤ x ≤ x_end. Find the minimum number of arrows that must be shot to burst all balloons.

Example:

Input:

[[10,16], [2,8], [1,6], [7,12]]

→

Output:

2

One arrow can burst balloons [1,6] and [2,8], and another arrow can burst [7,12] and [10,16]

Algorithm:

1. Sort balloons by their end positions to optimize arrow placement
2. Place first arrow at the end position of first balloon
3. Skip all balloons that can be burst by current arrow
4. Place new arrow when current one can't burst balloon

public int findMinArrowShots(int[][] points) {
    if (points.length == 0) 
        return 0;
    
    // Sort by end position using Integer.compare to prevent overflow
    Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));

    int arrowPos = points[0][1];
    int count = 1;
    
    // Check if current arrow can burst each balloon
    for (int i = 1; i < points.length; i++) {
        if (arrowPos >= points[i][0]) continue;
        count++;
        arrowPos = points[i][1];
    }
    
    return count;  
}

Complexity:

Time: O(n log n) | Space: O(1)