Fewest Shots to Burst Every Balloon
Problem
Balloons are taped to a wall, and each one spans the horizontal range [start, end]. A vertical shot fired at position x bursts every balloon with start less than or equal to x and x less than or equal to end. Return the fewest shots that burst every balloon.
Examples
Input: balloons = [[10, 16], [2, 8], [1, 6], [7, 12]]
Output: 2
Why: a shot at 6 bursts [2, 8] and [1, 6], and a shot at 12 bursts [7, 12] and [10, 16]Input: balloons = [[1, 2], [3, 4], [5, 6], [7, 8]]
Output: 4
Why: no two balloons overlapInput: balloons = [[1, 2], [2, 3], [3, 4], [4, 5]]
Output: 2
Why: edge case, balloons that only touch at an end can share a shot, at 2 and at 4Hints
0 / 3
Some shot must burst the balloon that ends first. Where along that balloon should it be fired so it bursts as many others as possible?
Fire it at the balloon's right end. Every balloon that starts at or before that point is burst too, because none of them can end earlier. That is the same argument as picking the meeting that finishes first.
Sort balloons by end. Walk them, remembering the position of the last shot. A balloon that starts after the last shot needs a new shot, fired at its own end. Count those shots.
Solution
This is interval scheduling seen from the other side: the fewest shots equal the most balloons that are pairwise apart, and both come from sorting by end. The balloon that ends first needs some shot, and firing at its end is never worse than firing earlier, since every balloon still standing ends at or after that point and the shot bursts all of those that have already started. Balloons that start at or before the last shot are burst by it, and the first one that starts after it forces a new shot at its own end. Sorting costs O(n log n), the walk is O(n), and space is O(n) for the sorted copy.
def fewest_shots(balloons):
shots, last = 0, None
for start, end in sorted(balloons, key=lambda b: b[1]): # earliest end first
if last is None or start > last: # the last shot misses this balloon
shots += 1
last = end # fire as late as this balloon allows
return shots
print(fewest_shots([[10, 16], [2, 8], [1, 6], [7, 12]])) # -> 2
print(fewest_shots([[1, 2], [3, 4], [5, 6], [7, 8]])) # -> 4
print(fewest_shots([[1, 2], [2, 3], [3, 4], [4, 5]])) # -> 2Stuck on the idea rather than the code? Interval Scheduling covers it.