Greedy Algorithms8 sections · 316 units
Open in Course

Minimum Arrows - The Idea

Grouping overlapping balloons

An arrow can burst multiple balloons if they overlap. We want to maximize balloons per arrow.

Here's like activity selection in reverse: group overlapping balloons together. Minimum arrows = number of groups of overlapping balloons. Equivalently: minimum arrows = nn - maximum "saved" balloons.

But there is a simpler view: shoot at the end of each group. Each non-overlapping group needs its own arrow. The problem is asking: how many non-overlapping groups exist?