Minimum Arrows to Pop All Balloons

medium intervals greedy sorting

Problem

Each balloon spans an interval [start, end] on the x-axis. A vertical arrow at coordinate x pops every balloon whose interval contains x. Return the minimum arrows. Sort by end coordinate; fire an arrow at the current end and skip every balloon whose start is ≤ that end.

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 min_arrows(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 minArrows(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 minArrows(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 minArrows(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;
}

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