Minimum Number of Arrows to Burst Balloons: Sort by End, Shoot Late

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.

The greedy rule

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

Why shooting at the end is safe

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.

Common slips

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.