Free Greedy lessonsGreedy · Stage 1 · Sort then choose · Step 2

Fewest arrows for balloons

Burst every balloon on a wall with the fewest vertical arrows, by shooting at the end of the first balloon that is still unburst. About 15 minutes.

Where to shoot

Balloons hang on a wall, each covering a stretch from a start to an end. An arrow flies straight up from one spot and bursts every balloon whose stretch includes that spot, ends included.

Take the balloon that ends first. Any arrow must hit it somewhere, and its right end is the best spot, since it reaches as far right as possible while still bursting that balloon.

Shoot at the earliest end, it still bursts the first balloon.

A spot further left: can only burst fewer balloons.

Count the arrows

Sort the balloons by right end. Shoot at the first one's end. Skip every balloon that starts at or before that spot, as it is already burst.

The first balloon that starts after the arrow needs a new one. Shoot at its end and repeat. The number of arrows fired is the answer. This is the meeting sweep again, with touching ends counting as a hit.

Starts at or before the arrow? already burst.

Starts after the arrow? fire a new arrow at its end.

In code

balloons.sort(key=lambda b: b[1])
arrow = None
count = 0
for start, end in balloons:
    if arrow is None or start > arrow:
        count += 1
        arrow = end

Balloons sorted by right end: [1, 4], [2, 5], [6, 9], [7, 10].

Fire the first arrow at 4, the right end of [1, 4].

Move 1 of 4

Quick check

Balloons [1, 2], [2, 3], [3, 4], [4, 5], sorted by end. How many arrows?

Show the answer

2. An arrow at 2 bursts the first two; an arrow at 4 bursts the last two.

Your problem

Fewest arrows

Balloons hang on a wall, each described by [start, end], the stretch it covers including both ends. An arrow shot straight up from position x bursts every balloon with start ≤ x ≤ end. Return the fewest arrows needed to burst them all.

Example

balloons = [[1, 4], [2, 5], [6, 9], [7, 10]] → 2

0 ≤ balloons.length ≤ 100,000 · -1,000,000,000 ≤ start ≤ end ≤ 1,000,000,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.