Pattern visualizer
Minimum Number of Arrows to Burst Balloons
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. 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..
Sort by end, shoot at the earliest end you can
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?".
1FUNCTION minArrows(points)2 points <- SORT_BY_END(points)3 arrows <- 14 arrowX <- points[0].end5 FOR i <- 1 TO LENGTH(points) - 16 IF points[i].start <= arrowX7 CONTINUE8 arrows <- arrows + 19 arrowX <- points[i].end10 RETURN arrows
← / → step · space play · Home restart