#452
Minimum Number of Arrows to Burst Balloons
Medium Sort by end
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Balloons span intervals on the x-axis. A vertical arrow at x bursts every balloon whose interval contains x (ends included). Return the fewest arrows needed.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: fewest arrows to pop all balloons.
Why this works: shoot at the end of the earliest-ending balloon; it pops every balloon that has already started.
Example: [[10,16],[2,8],[1,6],[7,12]] sorted by end
arrow at 6 pops [1,6], [2,8]arrow at 12 pops [7,12], [10,16] → 2 arrows
✦Hints open one at a time
Shoot each arrow as far right as possible: at the end of the earliest-ending balloon.
That arrow also bursts every balloon that starts at or before that point.
↗Approach
Sort by end. Shoot at the first end; skip balloons with start <= arrow; on the first balloon starting after the arrow, shoot again at its end.
</>Solution (Java)
import java.util.*;
class Solution {
public int findMinArrowShots(int[][] points) {
Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
int arrows = 1;
long arrow = points[0][1];
for (int[] p : points) {
if (p[0] > arrow) { // not hit by the current arrow
arrows++;
arrow = p[1];
}
}
return arrows;
}
}!Common mistake
Comparator a[1] − b[1] overflows with values near ±2^31. Use Integer.compare.
Complexity
- Time: O(n log n).
- Space: O(log n).
Topic: Greedy
🎬 Episodes 69–73: video coming soon