Balloons: minimum arrows in Python

Why this matters

Many real problems ask you to cover a set of ranges with as few points as possible. A maintenance crew wants to pick the fewest times to inspect a set of machines, where each machine can only be checked during a time window. A network tool wants the fewest access points so that every device is in range of one. A teacher wants the fewest meeting slots so that every student has a slot inside their free window.

Each of these is a version of the same question. You have a list of ranges on a line, and you need the smallest number of points so that every range contains at least one point.

A greedy algorithm solves this with a single rule. Each time, it makes the choice that looks best right now, and it never goes back to change an earlier choice. For this problem the rule is simple: place the next point as far to the left as the first unhandled range allows, and that point is the right end of that range. This lesson shows why that rule gives the smallest count, and how to write it in Python.

This lesson covers only the balloon problem. The next lesson, Merge intervals and insert an interval, uses sorting in a different way. Other greedy lessons in this module cover jump games, gas stations and coin systems.

The problem in plain words

Picture a number line, which is a straight line with numbers on it. A balloon is a flat piece of the line from a left number to a right number. For example, a balloon from 2 to 8 covers every point from 2 up to 8, including 2 and 8.

You stand at the left edge and shoot arrows straight up along the line. An arrow at position x pops every balloon that covers x. A balloon from 2 to 8 is popped by an arrow at 2, at 5, at 8, or at any other point between them, but not by an arrow at 9.

The task: given a list of balloons, find the smallest number of arrows that pops all of them.

Two terms need a definition before we go on.

An interval is a range from a start number to an end number. We also write it as [start, end], where both ends are included. The balloons in this problem are intervals.

Overlap means two intervals share at least one point. The intervals [1, 6] and [5, 9] overlap, because both cover 5 and 6. The intervals [1, 4] and [6, 9] do not overlap, because no number is in both.

Start with a small example

Take four balloons:

Balloon A: [1, 2]
Balloon B: [3, 4]
Balloon C: [5, 6]
Balloon D: [7, 8]

No two balloons overlap. Any arrow can pop only one of them. So you need four arrows. There is no way to do it in fewer.

Now take balloons that do overlap:

Balloon A: [1, 6]
Balloon B: [2, 8]
Balloon C: [7, 12]
Balloon D: [10, 16]

Look at the picture on the number line:

1       6
[=======A]
   2       8
   [=======B]
                   7        12
                   [========C]
                       10          16
                       [=========D]

Balloons A and B overlap between 2 and 6. One arrow at 6 pops both. Balloons C and D overlap between 10 and 12. One arrow at 12 pops both. So two arrows are enough. The question is how to find those two arrow positions in a way that always works.

The idea: shoot at the earliest end

The rule has three steps.

1. Sort all balloons by their end number, smallest first.
2. Shoot the first arrow at the end of the first balloon in the sorted list. Every balloon that covers that point is popped too.
3. Walk through the rest of the list. If a balloon starts after the last arrow, it is not popped yet. Shoot a new arrow at its end. Otherwise it is already popped, so skip it.

Try it on the example above. Sorted by end, the list is:

A: [1, 6]    end 6
B: [2, 8]    end 8
C: [7, 12]   end 12
D: [10, 16]  end 16

The first arrow goes at 6. Balloon A ends at 6, so it is popped. Balloon B starts at 2, which is at or before 6, so the arrow at 6 also covers B. Balloon C starts at 7, which is after 6, so the first arrow misses it. The second arrow goes at 12, the end of C. Balloon D starts at 10, which is before 12, so the second arrow pops it too. Total: 2 arrows.

The rule is called greedy because each arrow is placed as early as possible. Placing an arrow early leaves the most room for the balloons that come after it.

Why sort by the end point

Sorting by start is a natural first guess. It fails. Take this list:

A: [1, 10]
B: [2, 3]
C: [4, 5]

Balloon A is long and covers almost everything. Balloons B and C are short and do not overlap each other.

If you sort by start, A comes first. You shoot at 10 for A. B starts at 2, which is before 10, so it looks popped too. C starts at 4, which is also before 10, so it looks popped too. The count is 1.

That is wrong. One arrow at 10 does pop A, and it does not reach B at 3 or C at 5. Balloon B ends at 3, and an arrow at 10 is past it. So B and C need arrows of their own. The right answer is 2. An arrow at 3 pops A and B. A second arrow at 5 pops C.

Sorting by end avoids this. Short balloons come first, so an arrow placed at the end of the short balloon also reaches the long balloon, because a long balloon that starts before that point still covers it. The end point is the earliest place where you are forced to shoot, so ordering by end makes the first arrow as useful as it can be.

Why the choice is safe

A greedy rule only works if its first choice can always be part of a best answer. Here is the argument, in plain words.

Let balloon X be the balloon with the smallest end number. Let e be that end. Any solution must pop X with some arrow. Call that arrow at position p. Since X covers p, the position p is between the start of X and e. So p is at most e.

Now move that arrow from p to e. Check each balloon the arrow used to pop, call one of them Y.

• Y was popped at p, so Y starts at or before p. Since p is at most e, Y still starts at or before e.
• Y ends at or after p. Also, Y's end is at least e, because X has the smallest end. So Y still reaches e.

So after the move, Y is still popped. Every balloon that the old arrow popped is still popped by the new arrow. Nothing is lost. The number of arrows is the same, and one arrow now sits at e.

This means there is a best solution with an arrow at e. The greedy rule takes that arrow, removes every balloon it pops, and faces the same problem again with fewer balloons. Repeating the argument shows the greedy count is optimal. This kind of proof is called an exchange argument: you show that you can swap the optimal solution's first choice for the greedy choice without making things worse.

The Python code

Python has no built-in balloon type, but a dataclass does the same job. A dataclass is a small class that only holds data. You list its fields with type hints, and Python writes the constructor for you. A type hint is a note after a name, such as start: int, that says what kind of value the name should hold. Python does not enforce hints when it runs, but editors and checking tools use them.

frozen=True makes each balloon read-only after it is made. Trying to change a field raises an error, which is shown in the common mistakes.

Save the code as balloons.py, then run python3 balloons.py. The program prints 2. The last two lines run only when you start the file directly, so another file can import Balloon and min_arrows without the example running.

Read the code line by line.

• @dataclass(frozen=True) above the class builds the constructor and the fields. Balloon(2, 8) makes a balloon from 2 to 8. b.start and b.end read its fields.
• if not balloons: handles the empty list. An empty list counts as false in a condition. Without this check, ordered[0] would fail, as shown below.
• sorted(balloons, key=lambda b: b.end) returns a new list with the balloons in order of their end. The key= part tells sorted what value to compare. lambda b: b.end is a short unnamed function. Given a balloon b, it returns b.end.
• arrow_at holds the position of the current arrow. It starts at the end of the first balloon in the sorted list.
• ordered[1:] is a slice. It is a new list that holds every item from index 1 to the end. Index 0 is the first balloon, and it was already used to place the first arrow, so the loop starts after it.
• if balloon.start > arrow_at uses >, not >=. A balloon that starts exactly at arrow_at is still covered, because the arrow hits that exact number. This matters for touching balloons, covered below.

sorted() and list.sort() do different things. sorted() returns a new list and leaves the list you passed in alone. list.sort() changes the list it is called on. Exercise 5 shows what that does to the caller.

Worked example 1: the basic case

Start with four balloons that are easy to picture:

ex1 = [
    Balloon(10, 16),
    Balloon(2, 8),
    Balloon(1, 6),
    Balloon(7, 12),
]
print(min_arrows(ex1))

Sorted by end, the list is [1, 6], [2, 8], [7, 12], [10, 16].

The program prints:

2

Worked example 2: a long balloon with short ones inside

This case breaks the start-based rule, so it is a good test. Use the three balloons from the earlier section, [1, 10], [2, 3] and [4, 5].

print(min_arrows([Balloon(1, 10), Balloon(2, 3), Balloon(4, 5)]))

The function sorts them by end into [2, 3], [4, 5], [1, 10].

• The first arrow goes at 3. It pops [2, 3].
• [4, 5] starts at 4, which is after 3. A second arrow goes at 5. It pops [4, 5].
• [1, 10] starts at 1, which is at or before 5. The second arrow already covers it.

The program prints 2. A long balloon that contains shorter ones is handled by the same loop. It is popped on the way, because the arrow placed for a shorter balloon sits inside it.

Worked example 3: balloons that touch, and large numbers

Two balloons that share an end point still overlap at that point:

print(min_arrows([Balloon(1, 4), Balloon(4, 5)]))

The first balloon ends at 4, so the arrow goes at 4. The second balloon starts at 4. The check 4 > 4 is false, so the arrow covers it. The output is:

1

If you had written >= in the check, the code would add a second arrow, and the answer would be wrong.

Large numbers need less care in Python than in many other languages. An integer in Python has no size limit, so a subtraction never wraps around to a wrong negative number. Check this:

a = 2_000_000_000
b = -2_000_000_000
print("a - b =", a - b)
print("2 ** 100 =", 2 ** 100)

Output:

a - b = 4000000000
2 ** 100 = 1267650600228229401496703205376

The sort in this lesson still uses key=, not a hand-written subtraction. A key is shorter to read, and it works for any type that Python can compare, such as strings or fractions.

Worked example 4: seven balloons, step by step

The first three examples have four or fewer balloons. Here is a longer list, where balloons can sit inside each other and where some start before the arrow and some after:

seven = [
    Balloon(4, 9),
    Balloon(1, 3),
    Balloon(7, 8),
    Balloon(2, 6),
    Balloon(10, 12),
    Balloon(11, 15),
    Balloon(13, 14),
]
print(min_arrows(seven))

After sorting by end, the code sees this order:

[1, 3]   [2, 6]   [7, 8]   [4, 9]   [10, 12]   [13, 14]   [11, 15]

Walk through it the way the loop does:

The arrow at 3 pops [1, 3] and [2, 6]. The arrow at 8 pops [7, 8] and [4, 9], because [4, 9] starts before 8 and ends after it. The arrow at 12 pops [10, 12]. The arrow at 14 pops [13, 14] and [11, 15]. The program prints:

4

Notice that [4, 9] was popped by an arrow placed for a balloon that ended earlier. Notice also that [11, 15] came last in the sorted order but was popped by the arrow placed for [13, 14]. The loop does not need to know which balloon an arrow was placed for. It only needs to compare starts with the current arrow.

Sorting takes time that grows a little faster than the number of balloons. The loop after the sort takes one step per balloon. For most inputs, the sort is the expensive part, and the rest is quick.

A rule that looks reasonable but fails

A tempting idea is this: find the point covered by the most balloons, shoot there, remove the balloons it popped, and repeat. It sounds sensible, because one arrow pops the most balloons it can.

It is wrong. Take these five balloons: [6, 7], [7, 8], [0, 4], [4, 6] and [5, 9].

• Point 6 is covered by [6, 7], [4, 6] and [5, 9], which is three balloons. Point 7 is covered by [6, 7], [7, 8] and [5, 9], also three. Break the tie by taking the smaller point, 6.
• Shoot at 6. It pops [6, 7], [4, 6] and [5, 9]. Two balloons are left: [7, 8] and [0, 4]. They do not overlap, so two more arrows are needed.
• The total is 3.

But two arrows are enough. One arrow at 4 pops [0, 4] and [4, 6]. One arrow at 7 pops [6, 7], [7, 8] and [5, 9]. Each balloon is hit, and the total is 2.

The most-overlap rule takes a big early choice that blocks a better layout. The end-point rule never makes that kind of choice, because the exchange argument above shows that the earliest end is always safe to use. This is why the choice of sort key matters.

Checking the rule against brute force

A brute force check tries every possibility and keeps the best. For this problem, the possible arrow positions are the start and end numbers of the balloons. The brute force program tries every group of those positions, smallest groups first, until it finds one that pops every balloon.

from itertools import combinations
 
 
def brute_force(balloons):
    candidates = sorted({b.start for b in balloons} | {b.end for b in balloons})
    for k in range(1, len(candidates) + 1):
        for points in combinations(candidates, k):
            if all(any(b.start <= p <= b.end for p in points) for b in balloons):
                return k
    return 0

combinations(candidates, k) gives every group of k positions from the list. The check b.start <= p <= b.end is Python's way to say that p is between the two ends, both included.

Brute force is too slow for big inputs, but it is perfect for checking a small test. A check was run with random.seed(25), which fixes the random numbers so the run can be repeated. It used 2,000 random lists of 1 to 6 balloons. Each balloon's two numbers are random whole numbers from 0 to 11, and the smaller one is the start. The greedy code and the brute force agreed on every one of them: 2,000 of 2,000.

Common mistakes

Sorting by start instead of end. The example with [1, 10] shows the cost. If the sort key uses the start, the arrow is never moved earlier:

ordered = sorted(balloons, key=lambda b: b.start)

Used with the same loop, on the list [1, 10], [2, 3], [4, 5], this version prints 1. The correct answer is 2. The fix is to sort by b.end.

A comparison that returns True or False. A function passed to cmp_to_key must return a negative number, zero or a positive number. Here the function returns a boolean, and Python raises no error:

from functools import cmp_to_key
 
pairs = [Balloon(5, 9), Balloon(1, 3), Balloon(7, 8)]
bad = sorted(pairs, key=cmp_to_key(lambda a, b: a.end < b.end))
print([(b.start, b.end) for b in bad])

Output:

[(5, 9), (1, 3), (7, 8)]

The list comes back unchanged. True and False count as 1 and 0, so the function never returns a negative number, and Python never moves a balloon. A subtraction returns a negative number when the first end is smaller, so it sorts correctly:

good = sorted(pairs, key=cmp_to_key(lambda a, b: a.end - b.end))
print([(b.start, b.end) for b in good])

Output:

[(1, 3), (7, 8), (5, 9)]

The key=lambda b: b.end form used in min_arrows avoids this mistake, because it returns the value to compare and never a comparison result.

A misspelled field name. The field is end. Writing b.endpoint fails at run time:

sorted(pairs, key=lambda b: b.endpoint)

The last line of the error is:

AttributeError: 'Balloon' object has no attribute 'endpoint'

Check the spelling against the fields in the class.

Forgetting the empty case. An empty list has no first balloon. Without the guard, ordered[0] fails:

def no_guard(balloons):
    ordered = sorted(balloons, key=lambda b: b.end)
    return ordered[0].end
 
 
no_guard([])

The last line of the error is:

IndexError: list index out of range

The guard if not balloons: return 0 prevents it.

Using >= for the check. The check balloon.start >= arrow_at treats touching balloons as separate. The [1, 4] and [4, 5] example then prints 2 when the answer is 1.

Changing a frozen balloon. A Balloon cannot change after it is made, so this line fails:

b = Balloon(1, 2)
b.start = 9

The last line of the error is:

dataclasses.FrozenInstanceError: cannot assign to field 'start'

To move a balloon, make a new one, such as Balloon(9, b.end).

Practice

Exercise 1

Find the minimum number of arrows for these balloons: [1, 5], [2, 3], [4, 6], [7, 8].

Show the answer

Sorted by end: [2, 3], [1, 5], [4, 6], [7, 8]. The first arrow goes at 3, which pops [2, 3] and [1, 5]. Balloon [4, 6] starts at 4, which is after 3, so a second arrow goes at 6. Balloon [7, 8] starts at 7, which is after 6, so a third arrow goes at 8. The answer is 3. The program prints 3 for this input.

Exercise 2

Balloons [1, 10], [2, 3] and [4, 5] need 2 arrows. Explain in one or two sentences why sorting by start and keeping the first arrow where it is gives 1.

Show the answer

After sorting by start, the first balloon is [1, 10], so the arrow goes at 10. The next balloons, [2, 3] and [4, 5], both start before 10, so the rule treats them as popped. But an arrow at 10 is past both of their ends, so it does not reach them. The rule fails because it never moves the arrow earlier when a short balloon with an earlier end appears.

Exercise 3

Write a function arrow_positions(balloons) that returns the positions where the arrows go, in order. For the example [1, 6], [2, 8], [7, 12], [10, 16], it should return [6, 12].

Show the answer

def arrow_positions(balloons: list[Balloon]) -> list[int]:
    if not balloons:
        return []
    ordered = sorted(balloons, key=lambda b: b.end)
    arrow_at = ordered[0].end
    shots = [arrow_at]
    for balloon in ordered[1:]:
        if balloon.start > arrow_at:
            arrow_at = balloon.end
            shots.append(arrow_at)
    return shots

The number of positions it returns is the answer to min_arrows. For the example, the function returns [6, 12].

Exercise 4

Find the minimum number of arrows for [0, 0], [0, 0] and [1, 1].

Show the answer

Sorted by end, the list is the two [0, 0] balloons and then [1, 1]. One arrow at 0 pops both [0, 0] balloons, because each starts at 0 and the check 0 > 0 is false. Balloon [1, 1] starts at 1, which is after 0, so a second arrow goes at 1. The answer is 2. The program prints 2 for this input.

Exercise 5

The function below sorts the list it receives. Run it on a list and check what the caller sees afterwards. Then change it so the caller's list keeps its order.

def in_place(balloons):
    balloons.sort(key=lambda b: b.end)
    arrows = 1
    arrow_at = balloons[0].end
    for balloon in balloons[1:]:
        if balloon.start > arrow_at:
            arrows += 1
            arrow_at = balloon.end
    return arrows
 
 
orig = [Balloon(10, 16), Balloon(2, 8), Balloon(1, 6)]
print(in_place(orig), [(b.start, b.end) for b in orig])

Show the answer

The output is 2 [(1, 6), (2, 8), (10, 16)]. The call to balloons.sort(...) changes the list object that the caller passed in, so the caller now sees the sorted order.

The fix is to change the first line to ordered = sorted(balloons, key=lambda b: b.end) and to read ordered in the rest of the function. min_arrows already does this. After calling it on the list [(10, 16), (2, 8), (1, 6)], the caller still sees [(10, 16), (2, 8), (1, 6)].

Summary

• A balloon is an interval, and one arrow pops every balloon whose range includes the arrow's point.
• Sort the balloons by their end number, not their start number.
• Shoot an arrow at the end of the first unpopped balloon, and skip balloons that start at or before that point.
• The choice is safe, because moving any arrow to the earliest end keeps every balloon it popped.
• Use sorted() with a key= function, and keep > in the check so touching balloons count as covered.