Greedy Algorithms8 sections · 316 units
Open in Course

Problem - Minimum Arrows

Burst balloons

Balloons are represented as intervals on the x-axis. An arrow at position xx bursts all balloons where startxendstart \leq x \leq end. Find minimum arrows to burst all balloons.

Example: [[10,16], [2,8], [1,6], [7,12]]. One arrow at 66 bursts [2,8] and [1,6]. One arrow at 1111 bursts [10,16] and [7,12]. Total: 22 arrows.

How is this related to activity selection? Tricky: minimum arrows = number of non-overlapping groups. Each group of overlapping balloons needs one arrow.