452. Minimum Number of Arrows to Burst Balloons

452

MediumIntervals and Sweep LineSort by end, then sweep counting non-overlapping groupsGreedy interval point stabbing

Minimum Number of Arrows to Burst Balloons

Balloons are given as horizontal intervals points[i] = [xstart, xend]. An arrow shot straight up at position x bursts every balloon whose interval contains x (xstart <= x <= xend). Return the minimum number of arrows needed to burst all balloons.

Open official problem prompt ↗

In plain English

Cover a set of intervals with the fewest single points, where each point may pierce any interval that contains it.

Picture it like this

Imagine scheduling the fewest inspections so that every guest's stay is checked at least once. You inspect right when the earliest-departing guest is about to leave, catching everyone still present, then wait until someone new arrives after that moment.

Example

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Why: One arrow at x=6 bursts [1,6],[2,8]; another at x=12 bursts [7,12],[10,16].

Constraints

1 <= points.length <= 10^5points[i].length == 2-2^31 <= xstart <= xend <= 2^31 - 1

Pattern lesson

See the pattern, then code

Greedy interval point stabbing

↗

Intervals and Sweep Line

Meetings, schedules, overlapping ranges, resource allocation, or timeline events.. Sort balloons by end coordinate. Shoot an arrow at the smallest end you have not yet covered; it also bursts every later balloon that starts before that end. Only start a new arrow when a balloon begins strictly after the current arrow's position.

New words, made simpleKnow these before the algorithm

Point cover / stabbing: Choosing points so every interval contains at least one chosen point
Greedy by end: Committing to the smallest available right endpoint because it constrains future choices the least
Overlap: Two balloons share a common x if the later one's start is not beyond the earlier one's end

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Sort by start, group overlaps

Works but the running-minimum bookkeeping is error-prone compared to sorting by end.

Sort by start and shrink a running overlap window's right edge as you go.

Time O(n log n)Space O(1)

Best choiceSort by end, fire greedily

Cleanest correct greedy; the end coordinate is exactly where the next arrow should go.

Sort by end; each time a balloon starts past the last arrow, fire a new arrow at its end.

Time O(n log n)Space O(1)

The rule we keep true

Invariant

Every balloon processed so far has been burst by some fired arrow, and the last arrow is placed at the end coordinate of the balloon that triggered it.

Why this is correct

Reasoning

The balloon with the smallest end must be hit by some arrow; placing that arrow at its end coordinate is optimal because any position that bursts it and lies at or before its end can only burst a subset of what shooting exactly at its end bursts. By an exchange argument the greedy choice is never worse than an optimal one, so it stays optimal.

The algorithm in three movesSay these aloud before coding

1Sort the intervals by their end coordinate

sorted by end: [1,6],[2,8],[7,12],[10,16]

2Track the position of the most recent arrow, starting at negative infinity

arrow at 6 covers [1,6],[2,8]

3For each balloon, if its start is beyond the current arrow, fire a new arrow at this balloon's end

7 > 6 -> new arrow at 12

4Return the arrow count

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

[1,6]0

[2,8]1

[7,12]2

[10,16]3

1 · Readraw points

2 · AskOrder by end

3 · Update state[1,6],[2,8],[7,12],[10,16]

4 · Resultarrows=0, arrow=-inf

Key takeaway

After sorting by end, the first arrow sits at 6 and a second at 12 covers the rest.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Sort by end
Ordering by right endpoint lets each arrow commit to the earliest possible burst position.
2
Lines 4-5Initialize
Zero arrows and an arrow position at negative infinity so the first balloon always triggers a shot.
3
Lines 6-9Fire on demand
A balloon whose start exceeds the current arrow is untouched, so we fire a new arrow at its end coordinate.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single balloon returns 1
All balloons overlapping at one common point return 1
Completely disjoint balloons return n
Touching balloons like [1,2] and [2,3] share x=2 so one arrow suffices

Common beginner mistakes

Using strict '<' when comparing start to arrow, which wrongly treats touching balloons [a,b] and [b,c] as separate
Sorting by start instead of end and mishandling nested intervals
Integer overflow assumptions; using float('-inf') sidesteps the 32-bit endpoint range in Python

Check your understanding

If two balloons just touch, like [1,2] and [2,3], how many arrows are needed and why?

Minimum Number of Arrows to Burst Balloons

Minimum Number of Arrows to Burst Balloons

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Intervals and Sweep Line