Minimum Number of Arrows to Burst Balloons

Shoot as few vertical arrows as possible to burst every balloon: sort by end and shoot at the end of the first balloon not yet burst.

The idea

The balloon that ends first must be hit by some arrow, and that arrow can be no further right than its end. Shooting exactly at its end is the best choice: it still bursts it and reaches as far right as possible, so it also bursts every balloon that starts by then. Sorting by end turns this into one scan: shoot at the first balloon's end, skip every balloon that starts at or before the arrow, and shoot again at the next one that does not.

Code

public static int FindMinArrowShots(int[][] points) {
    Array.Sort(points, (x, y) => x[1].CompareTo(y[1]));
    int arrows = 1, arrowAt = points[0][1];
    for (int i = 1; i < points.Length; i++) {
        if (points[i][0] > arrowAt) {
            arrows++; arrowAt = points[i][1]; // out of reach: shoot again
        }
    }
    return arrows;
}

Tips

• Touching counts: a balloon [12, 16] is burst by an arrow at 12, so the test for a new arrow is start > arrowAt, not >=.
• This is Non-overlapping Intervals turned around: the number of arrows equals the largest set of balloons that pairwise do not overlap.
• Sorting by start also works, but then you must shrink arrowAt to min(arrowAt, end) for every balloon you merge.

In the .NET library

LeetCode's inputs reach int.MinValue and int.MaxValue, so x[1] - y[1] in the comparison would overflow; CompareTo is safe.