Sort balloons by where they end and shoot each arrow at the earliest end. It pops every balloon still overlapping it, so you need the fewest.
▼The problem
LeetCode 452 (Medium). Balloons are horizontal intervals [xstart, xend] on a wall. An arrow shot straight up at x bursts every balloon with xstart <= x <= xend (ends included). Return the minimum number of arrows that burst them all.
Examples (LeetCode's): [[10,16],[2,8],[1,6],[7,12]] → 2 (arrows at 6 and 12); [[1,2],[3,4],[5,6],[7,8]] → 4; [[1,2],[2,3],[3,4],[4,5]] → 2 (touching ends share an arrow: arrows at 2 and 4).
The solution
def find_min_arrow_shots(points):
points.sort(key=lambda b: b[1]) # by end
arrows, x = 1, points[0][1] # first arrow
for s, e in points[1:]:
if s > x: # untouched
arrows += 1
x = e # new arrow at its end
# else: already burst
return arrowsTranscript
Minimum Number of Arrows to Burst Balloons. Each balloon spans a wall from start to end. An arrow shot straight up at x bursts every balloon covering x, ends included. How few arrows burst them all?
Ten to sixteen, two to eight, one to six, seven to twelve: arrows at six and twelve burst all four. Spread-out balloons need one arrow each. Four touching end to end need just two: touching ends share an arrow.
A first guess: shoot where the most balloons overlap, then repeat. That's n squared work per arrow, and it can waste one: the busiest spot takes four, and the two leftovers need two more. Three, not two.
The key idea: sort by end. The first balloon to end needs an arrow. Its end is the best spot: that hits every balloon started by then. Same sort by end idea as Non-overlapping Intervals.
In code, shoot the first arrow at the first end. For each next balloon, if it starts after the arrow, shoot a new one at its end. Otherwise it's already burst.
Now the first wall, sorted by end. One to six ends first: arrow one at six. Two to eight starts before six: burst. Seven to twelve starts after six, so arrow two flies at twelve. Ten to sixteen: burst. Two arrows.
Sorting takes n log n time, then one pass. Beyond the sort, just an arrow and a count: constant space.
Sort by end, shoot at the end, skip what's burst. That's Minimum Number of Arrows to Burst Balloons.