Greedy — Minimum Number of Arrows to Burst Balloons
↗ LeetCode: Minimum Number of Arrows to Burst Balloons · Medium · pattern chapter →
Balloons span [xstart, xend]. Arrow at x bursts every balloon whose span contains x. Min arrows.
Example 1 — points=[[10,16],[2,8],[1,6],[7,12]] → 2Example 2 — points=[[1,2],[3,4],[5,6],[7,8]] → 4 (all disjoint) Example 3 — points=[[1,10],[2,3],[4,5]] → 1 (all overlap the first)
Constraints — 1 ≤ n ≤ 10⁵; -2³¹ ≤ x ≤ 2³¹−1. Brute try-every-arrow-position is O(n · range) = potentially 10⁵ · 2³² = 4·10¹⁴ ops. Sort + greedy is O(n log n) = 1.7·10⁶.
Interview timer00:00
Approach 1 — Brute try every subset of arrows
Intuition. For each subset of endpoints, check if the arrows placed there burst every balloon. Return the smallest valid subset size.
Complexity — Time O(2ⁿ · n) subset check; Space O(n). TLE past n=20. Just state as reference: "this is set-cover in disguise — greedy earliest-end wins."
Approach 2 — Sort by end + shoot at end of first alive (canonical)
Insight. Sort by xend. Shoot the first balloon at its end. That arrow bursts every balloon starting ≤ end. Move to first balloon starting > end.
Trap — use Integer.compare — subtracting can overflow when spans include INT_MAX/MIN.
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;
}Complexity — Time O(n log n); Space O(1). Say aloud in an interview: "canonical activity-selection variant — sort by end, greedy pick. Same template as Non-overlapping Intervals and Meeting Rooms II counting."
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Brute subsets | O(2ⁿ · n) | O(n) | TLE past n=20 |
| Sort + shoot | O(n log n) | O(1) | Canonical |
When to use which
- "Min points to hit all intervals" → sort by end + greedy.
- "Which balloons burst by each arrow" → track intervals per arrow.