Minimum Number of Arrows to Burst Balloons

Share

Balloons are represented as intervals [xstart, xend]. An arrow shot at x bursts all balloons containing x. Find the minimum number of arrows to burst all balloons.

Example 1
Input: [[10,16],[2,8],[1,6],[7,12]] → Output: 2
Example 2
Input: [[1,2],[3,4],[5,6],[7,8]] → Output: 4

Solution Approach

Greedy: sort by end. Shoot the arrow at the end of the first balloon. All overlapping balloons also burst. Move to the next unbursted balloon.

  • Sort by end time.
  • Shoot arrow at intervals[0][1]. Count = 1.
  • For each next interval: if its start > current arrow position, shoot a new arrow at its end, count++.
Java
import java.util.*;

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a,b) -> Integer.compare(a[1],b[1]));
        int arrows = 1, arrowAt = points[0][1];
        for (int[] p : points) {
            if (p[0] > arrowAt) { arrows++; arrowAt = p[1]; }
        }
        return arrows;
    }
}
  • Time Complexity: O(N log N)
  • Space Complexity: O(1)