Minimum Number of Arrows to Burst Balloons

Medium#452sort by end

Balloons hang over a line, each one covering an interval [start, end]. An arrow shot straight up at point x bursts every balloon with start ≤ x ≤ end, even one it only touches at the edge. Find the fewest arrows that burst all the balloons. Our example: [4, 8], [10, 12], [1, 6], [7, 9], [2, 4], [9, 11] — the answer is 3.

452 Minimum Number of Arrows to Burst BalloonsWalkthrough · 1×

Example: [4, 8], [10, 12], [1, 6], [7, 9], [2, 4], [9, 11]. The balloons are drawn sorted by end, and each arrow is a vertical line at the point it is shot from.

[2, 4][1, 6][4, 8][7, 9][9, 11][10, 12]0123456789101112
not looked at yetcurrent balloon, new arrowburst

Sort by end: 4, 6, 8, 9, 11, 12

01/18
restart · back · play · step
Speed
1function findMinArrowShots(points):
2 sort points by end
3 arrows = 1
4 arrowAt = points[0].end
5 for each [start, end] after the first:
6 if start > arrowAt:
7 arrows = arrows + 1
8 arrowAt = end
9 return arrows
state
arrows
–
arrowAt
–
start
–
end
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The balloon that ends first must be burst by some arrow at or before its end. Shooting exactly at its end loses nothing: every other balloon such an arrow could burst starts before that end and, ending later, still covers it.
  2. So each new arrow goes to the end of the first balloon the last arrow missed. A later balloon is missed only if it starts after arrowAt; one that starts at arrowAt is touched and bursts.
  3. Each new arrow is for a balloon that starts after the previous arrow, so the balloons that got arrows, [2, 4], [7, 9] and [10, 12], share no point. No arrow can burst two of them, so fewer than 3 arrows is impossible.

Complexity

Time O(n log n): the sort; the pass after it is O(n). Memory O(1) besides what the sort needs.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.