What it teaches: The same greedy from the other side: shoot at the earliest end, and that arrow bursts every balloon that started before it.
Practise it on judges as “Minimum Number of Arrows to Burst Balloons”.
The problem
Each balloon spans [xstart, xend] on the x-axis. An arrow shot at x bursts every balloon with xstart ≤ x ≤ xend. Return the minimum number of arrows to burst all balloons.
Example 1
Input: [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Example 2
Input: [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Constraints
1 ≤ n ≤ 10⁵
−2³¹ ≤ x ≤ 2³¹ − 1
Pattern clues in the wording
→ Cover all intervals with the fewest points
→ Touching counts as overlapping here
These clues point to Greedy Choice: Make the best-looking choice at each step and never undo it, after proving that this choice is always safe.
Stuck? Take one hint at a time
Solution.java · starter
import java.util.*;
class Solution {
public int findMinArrowShots(int[][] points) {
return 0;
}
}
Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.
Sort by end. arrows = 1, arrowAt = first end. For each balloon with start > arrowAt, shoot a new arrow at its end.
Approach 1
import java.util.Arrays;
class Solution {
public int findMinArrowShots(int[][] points) {
Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1])); // no subtraction: values span the int range
int arrows = 1;
long arrowAt = points[0][1];
for (int[] p : points) {
if (p[0] > arrowAt) {
arrows++;
arrowAt = p[1];
}
}
return arrows;
}
}
Verdict: Shooting as late as possible maximises the balloons each arrow bursts.
Before you submit
Edge cases and common mistakes
Test these inputs
Extreme values (comparator overflow with a − b)
Touching balloons share one arrow
One balloon
Mistakes people make
Comparator a[1] − b[1] overflowing for values near ±2³¹.