Minimum Arrows to Burst Balloons: Greedy on Overlaps

"Minimum Number of Arrows to Burst Balloons" is a Medium-level staple in Meta, Amazon, Bloomberg loops, and it is a textbook fit for the Merge Intervals pattern — one of the nine patterns that cover the bulk of what FAANG coding interviews actually test. Part 7 of 11 in the Merge Intervals arc.

The Problem

Balloons are horizontal diameter ranges [start, end]; an arrow shot at x bursts every balloon whose range contains x. Return the minimum arrows to burst all balloons. Equivalently: partition intervals into the fewest groups that each share a common point.

Input:  points = [[10, 16], [2, 8], [1, 6], [7, 12]]
Output: 2
Shoot x = 6 (bursts [2, 8] and [1, 6]) and x = 11 (bursts [10, 16] and [7, 12]).

Recognizing the Merge Intervals Pattern

Interval problems — scheduling, calendars, resource booking — almost all reduce to one move: sort by start (or end), then sweep once while comparing each interval against a running boundary. Overlap exists when the next start is at most the current end. Sort plus linear sweep, O(n log n), is the backbone of the entire family.

Fewest common points covering all intervals is the dual of Non-overlapping Intervals: sort by end, shoot at the first balloon's end, and every balloon starting at or before that point is handled. The greedy and its proof transfer wholesale.

The Approach

Sort by end. Shoot at the first end; skip every balloon whose start is at most the arrow position; the next surviving balloon defines the next arrow. Each arrow is placed as far right as the current group allows, which by the exchange argument can only help future balloons.

Overlap here includes touching — a balloon ending at 6 and one starting at 6 share point 6 — so the comparison is at-most, not strictly-less. Note the contrast with Non-overlapping Intervals, where touching was compatible.

Python Solution

def find_min_arrow_shots(points: list[list[int]]) -> int:
    """Fewest arrows (common points) to cover every interval."""
    if not points:
        return 0
    points.sort(key=lambda p: p[1])
    arrows = 1
    arrow_x = points[0][1]                 # shoot at earliest end
    for start, end in points[1:]:
        if start > arrow_x:                # not covered: new arrow
            arrows += 1
            arrow_x = end
    return arrows

Complexity

• Time: O(n log n) — sort by end, then one pass
• Space: O(1) — arrow position and a counter

Interview Tips and Follow-Ups

• Coordinates reach 2³¹ − 1 in the original problem — in other languages the sort comparator can overflow; in Python it cannot. Saying this shows cross-language awareness.
• Contrast with Non-overlapping Intervals in one sentence (touching differs, greedy identical) — interviewers love hearing the family resemblance stated.
• Variant to expect: arrows cost differently by position, which breaks the greedy and pushes you toward DP — recognize the boundary of the pattern.

More Merge Intervals problems — and the other eight patterns — live in the Technical Interview category. Drill the pattern, not the problem: that is the entire thesis of this series.