Minimum Number of Arrows to Burst Balloons

medium intervals greedy sorting

Problem

There are some spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it's horizontal, y-coordinates don't matter, and hence the x-coordinates of start and end of the diameter suffice.

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

Output2

Arrow at 6 pops [1,6] and [2,8]. Arrow at 12 pops [7,12] and [10,16].

balloons (e.g. "10,16; 2,8; 1,6; 7,12")

def find_min_arrow_shots(points):
    points.sort(key=lambda p: p[1])
    arrows = 1
    end = points[0][1]
    for s, e in points[1:]:
        if s > end:
            arrows += 1; end = e
    return arrows

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

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

int findMinArrowShots(vector<vector<int>>& points) {
    sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });
    int arrows = 1, end = points[0][1];
    for (int i = 1; i < (int)points.size(); i++) {
        if (points[i][0] > end) { arrows++; end = points[i][1]; }
    }
    return arrows;
}

Explanation

One vertical arrow pops every balloon whose interval it crosses, so we want as few arrows as possible. The greedy idea is to sort balloons by their end coordinate and fire an arrow at the end of the first one.

That arrow is placed at end, the smallest right edge, which pops the first balloon and any others that reach back over that point. We keep scanning: any balloon whose start is <= end is already pierced, so we reuse the same arrow.

Only when a balloon's start is strictly greater than end do we need a new arrow, fired at that balloon's end, and we update end to it.

Example: [[10,16],[2,8],[1,6],[7,12]] sorted by end is [1,6],[2,8],[7,12],[10,16]. An arrow at 6 pops the first two; 7 > 6 needs a second arrow at 12, which also covers [10,16], giving 2.

Shooting at the earliest end greedily covers the most balloons at once, which is why this minimizes the arrow count.

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