253. Minimum Number of Arrows to Burst Balloons

This is the classic interval point-cover problem. After sorting balloons by their ending coordinate, the first balloon's right edge is the earliest moment we must shoot. Shooting exactly there bursts every overlapping balloon — extending leftwards costs nothing. Then advance to the first balloon that starts after this shot and repeat.

Why sort by end, not start?

A greedy that shoots at every balloon's start as early as possible can over-shoot. Sorting by end and shooting at the first end-coordinate is provably optimal — among all the balloons that overlap the first one, shooting at its right end pops them all and delays as long as possible, leaving room for the most future balloons.

Steps

1. Edge case: if points is empty, return 0.
2. Sort points by x[1] (the end coordinate).
3. Initialise arrows = 1 and end = points[0][1] — we'll shoot at the first balloon's end.
4. For each subsequent balloon (s, e):
   • If s > end, this balloon's left edge is past the last arrow. We need a new arrow at e.
     • arrows += 1, end = e.
   • Otherwise the existing arrow at end already pops it (since s ≤ end ≤ e).
5. Return arrows.

Walk-through

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

After sort by end: [[1, 6], [2, 8], [7, 12], [10, 16]].

Result: 2 arrows. One at x=6 pops balloons [1,6] and [2,8]. One at x=12 pops [7,12] and [10,16]. ✓

Why an arrow at end covers all overlapping balloons

When we sort by end coordinate, every balloon with start s ≤ end includes the point end in its range (since s ≤ end ≤ its-own-end). So one arrow at end pops all of them.

Why > and not >=

"Touching" intervals like [1, 5] and [5, 10] count as overlapping at x = 5 per the problem statement — one arrow at x = 5 bursts both. The condition s > end correctly doesn't trigger a new arrow when s == end.

Edge cases

• Empty input: return 0.
• One balloon: one arrow.
• All balloons identical: one arrow pops them all.

Complexity

• Time: O(n log n) — sort dominates.
• Space: O(1) — in-place sort, two scalars.

import java.util.*;

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