Minimum Number of Arrows to Burst Balloons
Medium · Intervals · Array · Greedy · Sorting
Problem
Balloons are taped to a wall. Balloon i covers the horizontal range points[i] = [x_start, x_end]; their heights do not matter.
An arrow shot straight up from position x bursts every balloon with x_start <= x <= x_end and keeps flying. Return the fewest arrows that burst all the balloons.
Examples
Input: points = [[1,5],[3,7],[8,12],[10,11]] Output: 2
An arrow at 4 bursts the first two balloons, and an arrow at 10 bursts the last two.
Input: points = [[1,2],[2,3],[3,4]] Output: 2
An arrow at 2 bursts the first two (touching ends count); the third needs a second arrow at 3 or 4.
Input: points = [[-4,-1],[0,3]] Output: 2
The two balloons share no position, so each needs its own arrow.
Constraints
- 1 <= len(points) <= 10^5
- points[i] == [x_start, x_end]
- -2^31 <= x_start < x_end <= 2^31 - 1
Approaches
- Shoot at the earliest end, then rescan — time O(n²), space O(n)
Follow-up
What if you also had to report where to shoot? The greedy already knows: every arrow it counts is fired at the end of the balloon that triggered it, so collecting those ends gives one optimal set of positions.
Related problems
Start free on Cariara · Coding problems · System design studio
