Balloons: minimum arrows

Why this matters

Picture a flat wall with balloons stuck on it. Each balloon is a horizontal strip. An archer stands below the wall and shoots an arrow straight up at one position along the wall. The arrow pops every balloon whose strip covers that position. The archer wants to pop all the balloons with as few arrows as possible, because arrows cost money.

This problem is a standard greedy exercise. It is short to code, and it teaches a proof technique you will use again in later greedy lessons. The first lesson in this module, on activity selection, asked you to keep as many meetings as possible. Here you ask the opposite question. You want to cover every item with as few points as possible.

Words you will need

• Interval: a span with a left end and a right end. A balloon is an interval on the wall.
• Closed interval: an interval that includes both of its ends. This lesson writes [start, end] and means that the point start and the point end both count. This is different from the half-open intervals in the activity selection lesson, where the right end does not count.
• Arrow: a single point on the wall. An arrow at position x pops every balloon with start less than or equal to x and end greater than or equal to x.
• Touching: two closed intervals touch when they share one point. [1, 6] and [6, 8] touch at 6. One arrow at 6 pops both.
• Exchange argument: a proof method. You take any answer that might be best and change one piece of it, step by step, until it matches the greedy answer. If no change makes the answer worse, the greedy answer is also best.
• Brute force: trying every possible answer and keeping the best one.

One example, worked by hand

Take four balloons: [1, 6], [2, 8], [7, 12] and [10, 16]. Before you read any code, try to cover them with as few arrows as you can.

Start with the balloon [1, 6]. Some arrow has to hit it, so place an arrow somewhere in its strip. Where should it go? The arrow pops every balloon that covers its spot. If you place it at 6, which is the right end of [1, 6], it also covers [2, 8], because 6 lies between 2 and 8. So one arrow has popped two balloons.

Next look at the balloons not yet popped. [7, 12] starts at 7, which is after 6, so the arrow at 6 misses it. A new arrow is needed. Place it at 12, the right end of [7, 12]. That arrow also covers [10, 16], because 12 lies between 10 and 16.

Two arrows pop all four balloons. The two arrows sit at 6 and 12. Could one arrow do the job? No. The balloons [1, 6] and [10, 16] have no common point, so one arrow cannot reach both.

Notice the pattern. Each arrow was placed at the right end of the first balloon in a group. The group is every balloon that the arrow reaches. The next arrow goes at the right end of the first balloon the first arrow missed. This pattern becomes the greedy rule.

The idea: sort by right end

The greedy rule is short. Sort the balloons by their right end, smallest first. Then walk down the list. Keep the position of the newest arrow. For each balloon, ask whether the newest arrow already pops it. If it does, skip the balloon. If it does not, shoot a new arrow at this balloon's right end.

Why does a balloon with a small right end matter most? A balloon whose right end is early is the hardest to reach later. Any arrow that pops it must sit at or before its right end. Placing the arrow exactly at that right end gives the arrow the most room to also pop balloons that start earlier.

Let us check that the walk gives the right result on the four balloons above. After sorting by right end, the order is [1, 6], [2, 8], [7, 12], [10, 16]. This order happens to match the input here, but the code will sort it anyway.

Step 1 shoots an arrow at 6, because the list of arrows is empty. Step 2 looks at [2, 8]. Its start is 2, which is at or before 6, so the arrow at 6 pops it. Skip. Step 3 looks at [7, 12]. Its start is 7, which is after 6, so the arrow at 6 misses it. Shoot a new arrow at 12. Step 4 looks at [10, 16]. Its start is 10, which is at or before 12, so the arrow at 12 pops it. Skip. The final count is 2.

Why the rule is correct

Sorting by right end is not a guess. You can prove that the greedy answer is never worse than any other answer. Here is the proof in plain steps.

Let B1 be the balloon with the smallest right end. Call that right end e1. Any valid set of arrows must pop B1, so some arrow sits somewhere inside B1's strip. Call that arrow's position x. Since x is inside the strip, x is at or before e1.

Now move that arrow from x to e1. Does anything break? Every balloon that the arrow used to pop is still popped. Take any such balloon, with left end s and right end e. It was popped at x, so s is at or before x. Because x is at or before e1, the left end s is at or before e1. Because B1 has the smallest right end, e is at or after e1. So e1 lies between s and e, and the balloon is still popped at e1.

After the move, the first arrow sits at e1. This is exactly the first arrow that the greedy walk places. The other arrows in the solution must pop every balloon that e1 does not pop. Those leftover balloons form a smaller version of the same problem. The greedy walk solves that smaller problem the same way. The leftover balloons form a shorter list, so the same argument applies to them, and by repeating it the greedy walk uses the fewest arrows on that list too.

So no solution can beat the greedy count. Greedy is optimal.

Program 1: the greedy in C++

The program reads the balloons, sorts them by right end, and prints the arrow positions. Type the four-balloon input below into the Input box, then press Run.

4
10 16
2 8
1 6
7 12

The first number is the count of balloons. Each of the next lines holds one balloon: its left end, then its right end. The lines are not in sorted order on purpose, so you can see the sort at work.

The output you should see:

arrows: 2
shoot at x = 6
shoot at x = 12

Here is what each part does. struct Balloon groups a left end and a right end under one name. The loop for (Balloon& b : balloons) reads each balloon. The & means the loop variable is the real balloon in the vector, not a copy. The sort call uses a lambda that compares right ends, which is the greedy rule written in code. The vector shots holds the positions where arrows were placed. The only test in the walk is b.start > shots.back(). If the balloon starts after the newest arrow, the arrow misses it, and a new arrow goes at its right end.

The shots.empty() test handles the first balloon. An empty vector has no back() element, so the program must not ask for one. Without this test the program would read memory that does not hold an arrow.

A second example: a chain of touching balloons

The next example is a little harder, because every balloon touches the next one. Balloons [1, 2], [2, 3], [3, 4] and [4, 5] form a chain. Each pair shares one point, and no single point is shared by more than two balloons. Work out the answer before you run the code.

Two arrows are enough. One at 2 pops the first two balloons, since both contain 2. One at 4 pops the last two, since both contain 4. A single arrow cannot do it, because [1, 2] and [4, 5] have no common point.

Paste this input into the Input box and press Run on Program 1 again:

4
1 2
2 3
3 4
4 5

The output you should see:

arrows: 2
shoot at x = 2
shoot at x = 4

The walk shoots at 2, skips [2, 3] because its start 2 is not after 2, shoots at 4 because [3, 4] starts at 3, which is after 2, and skips [4, 5] because its start 4 is not after 4. The count matches the hand answer.

A third example: a long balloon hiding short ones

The third example is the one where the long balloon matters. Take three balloons: [1, 10], [2, 3] and [4, 5]. The long balloon covers everything in the middle of the wall. A naive guess is to shoot at the long balloon's far end, at 10. That arrow misses both short balloons, because their right ends are 3 and 5.

The greedy rule sorts by right end, so the short balloons come first. The arrow goes at 3, which pops [2, 3]. Then [4, 5] starts at 4, which is after 3, so a second arrow goes at 5. The arrow at 5 also pops the long balloon [1, 10], because 5 lies between 1 and 10. The answer is 2.

Here is the run on that input:

3
1 10
2 3
4 5

arrows: 2
shoot at x = 3
shoot at x = 5

The example shows a useful fact. A long balloon is often popped for free by an arrow placed for a shorter one. The greedy rule does not need to care about the long balloon, because the sort puts it last and the arrow that reaches it is already in place.

How to check an answer

A greedy answer should be checked on small cases, because a wrong rule can look right on one example. The check used for this lesson is a brute force program, which tries every set of arrow positions. For a small list of balloons, every arrow position can be taken from the right ends of the balloons. The brute force program tries every subset of those positions and keeps the smallest subset that pops every balloon.

Brute force is too slow for large lists, but it is a reliable reference for small ones. Run 300 random lists of up to eight balloons through both programs. The greedy program and the brute force program gave the same count every time. This does not prove the rule, which the earlier section did, but it catches code mistakes quickly.

Common mistakes

Sorting by left end instead of right end. The most common wrong answer comes from sorting by the start of each balloon. Sorting by start puts the long balloon [1, 10] first in the three-balloon example above. The first arrow then goes at 10, and it misses both short balloons. The program then prints one arrow for all three balloons, which is wrong. Always sort by the right end.

Using >= where > is needed. The test for a new arrow is b.start > shots.back(). The strict greater-than sign is correct because the balloons are closed intervals. A balloon that starts exactly at the arrow position is still popped. If you change the test to >=, touching balloons get a separate arrow. Run this two-balloon input, [1, 3] and [3, 5], and the wrong version prints two arrows:

arrows: 2
shoot at x = 3
shoot at x = 5

The correct version prints one arrow at 3. The two balloons share the point 3.

Forgetting to sort before the walk. Without the sort, the walk takes the balloons in the order they were typed. An unsorted list can put a long balloon before a short one, and the arrow placed at the long balloon's end misses the short one. The sort is part of the rule, not an optional speed step.

Calling back() on an empty vector. When shots is empty, shots.back() refers to an element that does not exist. C++ does not check this for you, and the compiler does not warn about it under -Wall. The program may print junk, crash, or appear to work by luck. The shots.empty() test in Program 1 prevents this.

Mixing up the sort comparator. A comparator that returns <= instead of < breaks the strict order that sort needs. Use < for the comparator, as in a.end < b.end.

Sorting a struct without a comparator. If you call sort on a vector of structs and give it no comparator, the compiler stops. Here is one of the error lines that g++ 15.2 printed for a two-item vector of Interval structs with a plain sort(items.begin(), items.end()) call. The file path is trimmed:

predefined_ops.h:45:23: error: no match for ‘operator<’ (operand types are ‘Interval’ and ‘Interval’)

The message means sort does not know how to compare two Interval values. Add a lambda that says which field to compare, as Program 1 does.

Practice

Exercise 1. Four balloons are [1, 2], [3, 4], [5, 6] and [7, 8]. No two balloons touch or overlap. How many arrows are needed?

Show the answer

Four. Each balloon needs its own arrow, because no point is shared by two balloons. The program prints arrows at 2, 4, 6 and 8.

Exercise 2. Use the greedy rule by hand on [1, 3], [3, 5] and [5, 7]. Where do the arrows go?

Show the answer

Two arrows. The first arrow goes at 3, which pops [1, 3] and [3, 5], since both contain 3. The second arrow goes at 7, which pops [5, 7], since 7 lies inside it. The arrow at 3 does not reach [5, 7], because 3 is before 5.

Exercise 3. Find the minimum number of arrows for [0, 4], [1, 2], [3, 3] and [5, 6]. Work by hand first, then check with Program 1.

Show the answer

Three arrows, at positions 2, 3 and 6. The sorted order by right end is [1, 2], [3, 3], [0, 4], [5, 6]. The arrow at 2 pops [1, 2]. The balloon [3, 3] starts at 3, which is after 2, so the arrow goes at 3. That arrow also pops [0, 4], since 3 lies inside it. The balloon [5, 6] starts at 5, which is after 3, so a third arrow goes at 6. Program 1 prints the same three positions.

Exercise 4. Why does the greedy walk always shoot at a right end, and never at a point in the middle of a balloon?

Show the answer

The exchange argument answers this. Take any arrow in a valid solution and slide it right until it reaches the smallest right end among the balloons it pops. Every balloon it popped is still popped, because each one starts at or before the old position and ends at or after the new one. So a right end is always as good as any other spot, and the greedy walk can choose right ends without losing anything.

Exercise 5. For the input in Program 1, count how many balloons each arrow pops. Use the arrow positions 6 and 12.

Show the answer

The arrow at 6 pops [1, 6] and [2, 8], so two balloons. The arrow at 12 pops [7, 12] and [10, 16], so two balloons. The total is four, which matches the number of balloons. Every balloon is popped by at least one arrow.

Summary

• A closed interval includes both of its ends, so touching balloons share a point that one arrow can pop.
• Sort balloons by their right end, then shoot one arrow at the right end of each balloon that the newest arrow misses.
• The exchange argument shows that moving any arrow to the smallest right end keeps every balloon it popped, so greedy is optimal.
• The test b.start > shots.back() is the whole decision, and the strict > is required for touching balloons.
• Check a greedy rule against brute force on small random inputs before you trust it.