You get balloons as horizontal intervals [start, end]. An arrow shot at x bursts every balloon with start <= x <= end. Return the fewest arrows needed.
Sort by end point. Shoot the first arrow at the end of the first balloon, as late as possible. Every balloon whose start is at or before that point is already burst. The first balloon that starts after it needs a new arrow, again at its own end.
def find_min_arrow_shots(points):
points.sort(key=lambda p: p[1])
arrows, last = 0, float("-inf")
for start, end in points:
if start > last:
arrows += 1
last = end
return arrows
The balloon with the smallest end must be hit by some arrow, and that arrow cannot be later than its end. Moving the arrow right up to that end only adds balloons it hits, never removes any, because every other balloon ends later. That exchange argument is the whole proof, and saying it in two sentences is what interviewers listen for.
min; sorting by end is simpler.[1,2] and [2,3] share one arrow, so the test is start > last, not >=.-inf for the initial value; real inputs can include the minimum 32-bit integer.Complexity is O(n log n) for the sort and O(1) extra space. The same pattern solves Non-overlapping Intervals: the answer there is n - arrows.
Written by the team behind Linkjob.ai, which builds tools for interview practice. Notes are original and free to share.