Minimum Number of Arrows to Burst Balloons

You are given intervals representing balloons. Each balloon is [x_start, x_end]. An arrow shot at position x bursts all balloons where x_start <= x <= x_end.

Return the minimum number of arrows needed to burst all balloons.

Why this is worth learning

An arrow position must hit the earliest-ending remaining balloon. Move that mandatory arrow as far right as possible, to its end, without losing any useful earlier coverage.

Before coding: one-minute experiment

How many arrows are needed for [[1,2],[2,3]], and where can the arrow be placed?

Function signature

func FindMinArrowShots(points [][]int) int

Inputs / outputs

• points: list of balloon intervals.
• Return: minimum number of arrows.

Example

points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2

Arrows at x=6 and x=12.

Constraints

• 0 <= len(points) <= 100_000
• -1_000_000_000 <= x_start <= x_end <= 1_000_000_000

Core idea (near-solution)

Sort by end coordinate and greedily shoot an arrow at the end of the first balloon, then skip all balloons it bursts.

Invariant: every processed balloon is hit by an arrow already selected. The most recent arrow is at the earliest end of its group; any later balloon with start at or before that arrow also contains it, because ends are sorted.

Algorithm (step-by-step)

1. Sort balloons by end ascending.
2. Initialize arrows = 0 and lastEnd = -inf.
3. For each balloon:
   • If start > lastEnd, you need a new arrow. Increment arrows and set lastEnd = end.
   • Else, it is already burst by the current arrow.
4. Return arrows.

Correctness sketch

Let e be the smallest end among unburst balloons. Every solution needs some arrow x within that earliest-ending balloon, hence x<=e. Any remaining balloon hit by x has start<=x<=e and end>=e by minimality, so it is also hit by an arrow moved to e. This exchange loses no coverage and establishes an optimal solution whose next arrow is at e. Remove all balloons containing e and repeat. In end-sorted order, a balloon needs a new arrow exactly when its start is greater than the current arrow position. Counting these necessary greedy choices yields the minimum.

Trace (hand walkthrough)

Example input:
points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2

Arrows at x=6 and x=12.

Walk:
- sort by end: [1,6],[2,8],[7,12],[10,16]
- arrow at x=6 bursts first two
- next arrow at x=12 bursts last two -> total 2

Pitfalls to avoid

• Sorting by start instead of end.
• Using >= instead of > for overlap (touching at a point should be considered burst).

Debugging lens

Do not use >= when deciding to start another arrow; endpoint contact is sufficient. Test duplicate balloons, point balloons, nested ranges, and empty input.

Complexity

Time: O(n log n) for sorting plus a linear scan. Auxiliary space: O(log n) sorting stack and O(1) scan state. The reference sorts the outer points slice in place.

Implementation notes (Go)

• Sort by end coordinate.
• Start a new arrow only when start > currentEnd.

Reconstruction checkpoint

How many arrows are needed for [[1,2],[2,3]], and where can the arrow be placed?

Return to Intervals · Module quiz