Minimum Number of Arrows to Burst Balloons: Greedy Interval Strategy

LeetCode 452, Minimum Number of Arrows to Burst Balloons, gives you a list of balloons represented as horizontal intervals on the x-axis. Each balloon covers a range [xstart, xend]. An arrow shot vertically at position x bursts every balloon whose range includes x. Your goal: find the minimum number of arrows needed to burst all balloons.

Why this problem matters

This is a classic greedy interval problem dressed up in a fun scenario. At its core, you are grouping overlapping intervals and asking: how many groups are there? Each group of mutually overlapping balloons can be burst by a single arrow.

If you have worked through Merge Intervals or Non-overlapping Intervals, you already know the foundational technique: sort intervals by one endpoint and scan. The twist here is that instead of merging or removing intervals, you are counting the minimum number of "piercing points" that hit every interval at least once. This is the interval point cover problem, and it has a clean greedy solution.

The pattern also shows up in scheduling and resource allocation problems. Any time you need to cover a set of ranges with the fewest points, you are solving this same problem.

The key insight

Sort the balloons by their right endpoint. Then scan through them. Place your first arrow at the end of the first balloon. For each subsequent balloon, check if its start is past the current arrow position. If it is, you need a new arrow, and you place it at the end of that balloon. If the balloon starts at or before the arrow position, the existing arrow already bursts it.

Why sort by end point? Because placing the arrow at the rightmost possible position within the first balloon gives it the best chance of also hitting subsequent balloons. An arrow at the right edge of a balloon is optimal: it covers the current balloon and reaches as far right as possible into the next ones.

def findMinArrowShots(self, points):
    if not points:
        return 0

    points.sort(key=lambda x: x[1])
    arrows = 1
    end = points[0][1]

    for start, finish in points[1:]:
        if start > end:
            arrows += 1
            end = finish

    return arrows

Visual walkthrough

Let's trace through [[10,16],[2,8],[1,6],[7,12]]. After sorting by end position, we get [[1,6],[2,8],[7,12],[10,16]].

The algorithm finds two groups of overlapping balloons. The first arrow at x=6 passes through both [1,6] and [2,8]. The second arrow at x=12 passes through both [7,12] and [10,16]. Two arrows, all balloons burst.

Notice the comparison uses start > end (strictly greater than). A balloon that starts exactly at the arrow position is still burst by that arrow. This matches the problem definition: a balloon at [xstart, xend] is burst by an arrow at x if xstart <= x <= xend.

Complexity analysis

The sort dominates at O(n log n). The greedy scan is a single O(n) pass. Space is O(1) beyond the input (or O(n) if the sort is not in-place). Python's Timsort uses O(n) auxiliary space, but the algorithm itself only needs a counter and a single variable for the current arrow position.

The building blocks

Greedy interval covering

The core pattern is: sort by end, place a point at the end of the first uncovered interval, and skip everything that point already covers. This is the interval point cover greedy, which is the dual of the activity selection greedy used in Non-overlapping Intervals. In activity selection you maximize the number of non-overlapping intervals. Here you minimize the number of points that hit all intervals. Both rely on end-time sorting and a single left-to-right scan.

Sort-first overlap detection

Sorting intervals turns pairwise overlap detection from O(n^2) into a linear sweep. Once sorted by end, you only compare each interval against one boundary value. The same principle powers Merge Intervals (sort by start, merge neighbors) and Non-overlapping Intervals (sort by end, count removals). The only thing that changes is what you do when you find an overlap.

Edge cases to watch for

• Empty input. Return 0. No balloons means no arrows needed.
• Single balloon. Return 1. One arrow suffices.
• All balloons overlap at a single point. Something like [[1,5],[2,6],[3,7]]. One arrow at x=5 (end of the first sorted balloon) hits all three. Answer: 1.
• No overlaps at all. Each balloon is isolated. You need one arrow per balloon. Answer: n.
• Balloons touching at endpoints. [1,2] and [2,3] overlap at x=2. One arrow at x=2 bursts both. The condition start > end (not start >= end) handles this correctly.
• Negative coordinates. The algorithm works without modification since it only compares values.

From understanding to recall

You have seen the greedy interval covering pattern: sort by end, shoot at the end of the first uncovered balloon, and skip everything the arrow already reaches. The logic is nearly identical to Non-overlapping Intervals, but the question is flipped. Instead of counting intervals to remove, you count "pierce points" to add.

The detail that matters most is the comparison operator. Using start > end (strictly greater) means balloons that just touch at a boundary share the same arrow. This is what the problem requires, and getting it wrong changes the answer.

Practicing this problem alongside Merge Intervals and Non-overlapping Intervals builds a strong mental model of the interval greedy family. When you see a new interval problem in an interview, you will recognize which variant it is and know exactly which endpoint to sort by.

Related posts

• Merge Intervals - The foundational interval problem: sort by start time and merge overlapping ranges
• Non-overlapping Intervals - Greedy interval scheduling to minimize removals
• Meeting Rooms II - Count maximum concurrent overlaps using a sweep line with a heap