Minimum Number of Arrows to Burst Balloons [Medium] — Greedy Intervals

Problem Statement

Balloons are [xstart, xend] intervals. An arrow shot at x bursts all balloons with xstart <= x <= xend. Find minimum arrows.

Input: [[10,16],[2,8],[1,6],[7,12]] → Output: 2

Intuition

Sort by end. Shoot one arrow at end of first balloon. Skip all overlapping balloons. When a balloon's start > current end, shoot another arrow.

Solutions

C++

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

Java

public int findMinArrowShots(int[][] points) {
    Arrays.sort(points,(a,b)->Integer.compare(a[1],b[1]));
    int arrows=1; long end=points[0][1];
    for (int[] p:points) if(p[0]>end){arrows++;end=p[1];}
    return arrows;
}

JavaScript

var findMinArrowShots = function(points) {
    points.sort((a,b)=>a[1]-b[1]);
    let arrows=1, end=points[0][1];
    for (const [s,e] of points) if(s>end){arrows++;end=e;}
    return arrows;
};

Python

def findMinArrowShots(points: list[list[int]]) -> int:
    points.sort(key=lambda x: x[1])
    arrows, end = 1, points[0][1]
    for s, e in points:
        if s > end:
            arrows += 1
            end = e
    return arrows

Complexity

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