40. Minimum Arrows to Burst Balloons
Choose positions on the number line at which to shoot arrows. An arrow bursts every balloon whose closed interval contains its position; burst all balloons using as few positions as possible.
An arrow shot at a shared endpoint can hit both intervals. The answer counts arrow positions, not the total number of balloons or interval overlaps.
Example 1
Input
[[10,16],[2,8],[1,6],[7,12]]
Output
2
Explanation: Arrows at 6 and 12 cover all four closed intervals.
Example 2
Input
[[1,2],[2,3]]
Output
1
Explanation: One arrow at the shared closed endpoint hits both.
Constraints
0 <= balloons.length <= 105balloons[i].length == 2-231 <= start <= end <= 231 - 1
Hints
Hint 1
Which uncovered balloon imposes the earliest rightmost allowed shot?
Hint 2
Can an optimum’s shot be moved to that end without losing its covered balloons?
Hint 3
Sort by end and shoot only when the current closed interval starts beyond the last arrow.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Earliest endpoints give two shots
[[10,16],[2,8],[1,6],[7,12]]
2