Minimum Number of Arrows to Burst Balloons

Sort by end, shoot at the earliest end you can

time O(n log n)space O(n)

This is a minimum hitting-set problem in disguise, and on intervals the greedy choice is provably optimal: among the balloons still floating, the one that ENDS first must be hit by some arrow, and firing at exactly its end point is the furthest right that arrow can go — so it pops every balloon any other valid shot would, and possibly more. Sort by end once, keep the current arrow's x, and only spend a new arrow when a balloon starts after it. A balloon that merely touches the arrow (start equal to the arrow's x) is still hit.

Details

Animated on: balloons = [10,16], [2,8], [1,6], [7,12], [8,10], [3,4], [15,18] — an arrow fired straight up at x pops every balloon whose [start, end] covers x. Find the fewest arrows that pop all of them.

Problem:Minimum Number of Arrows to Burst BalloonsMedium

Pattern:Intervals

Sort by end, shoot at the earliest end you can

step 1 / 10

10..16

[0]

2..8

[1]

1..6

[2]

7..12

[3]

8..10

[4]

3..4

[5]

15..18

[6]

7 balloons, each spanning [start..end] on the x-axis, given in arbitrary order: 10..16, 2..8, 1..6, 7..12, 8..10, 3..4, 15..18. One arrow fired at x pops every balloon whose span covers x, so the question is really "how few x values touch all 7 spans?".

Pseudocode

1FUNCTION minArrows(points)
2  points <- SORT_BY_END(points)
3  arrows <- 1
4  arrowX <- points[0].end
5  FOR i <- 1 TO LENGTH(points) - 1
6    IF points[i].start <= arrowX
7      CONTINUE
8    arrows <- arrows + 1
9    arrowX <- points[i].end
10  RETURN arrows

← / → step · space play · Home restart

Every step in words

Show all 10 steps

7 balloons, each spanning [start..end] on the x-axis, given in arbitrary order: 10..16, 2..8, 1..6, 7..12, 8..10, 3..4, 15..18. One arrow fired at x pops every balloon whose span covers x, so the question is really "how few x values touch all 7 spans?".
Sorted by END: 4, 6, 8, 10, 12, 16, 18. Firing at the earliest end is never worse than firing anywhere else in that balloon — any balloon a further-right shot would catch, this shot catches too, plus possibly more. So one left-to-right sweep is enough and no choice ever has to be revisited.
3..4 ends soonest, so nothing is gained by waiting: fire arrow 1 at x = 4. arrows = 1.
1..6 starts at 1 <= 4, so the arrow already in the air at x = 4 passes through it. Free pop, arrows stays 1.
2..8 starts at 2 <= 4, so the arrow already in the air at x = 4 passes through it. Free pop, arrows stays 1.
8..10 starts at 8, to the right of the arrow at x = 4 — that shot could never reach it, so this balloon forces a new one. Fire at x = 10, its own end, for the same reason as before. arrows = 2.
7..12 starts at 7 <= 10, so the arrow already in the air at x = 10 passes through it. Free pop, arrows stays 2.
10..16 starts at 10 <= 10, so the arrow already in the air at x = 10 passes through it — touching at exactly one point still counts as a hit. Free pop, arrows stays 2.
15..18 starts at 15, to the right of the arrow at x = 10 — that shot could never reach it, so this balloon forces a new one. Fire at x = 18, its own end, for the same reason as before. arrows = 3.
Sweep finished: 3 arrows burst all 7 balloons. Each new arrow was forced by a balloon no earlier shot could reach, so no smaller number can exist.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Minimum Number of Arrows to Burst Balloons in the editor All Greedy problems Back to roadmap