Greedy Algorithms8 sections · 316 units
Open in Course

Minimum Arrows - Walkthrough

Tracing the algorithm

Balloons: [[10,16], [2,8], [1,6], [7,12]]. Sorted by end: [[1,6], [2,8], [7,12], [10,16]]. 1.1. Arrow 11 at position 66. Bursts [1,6] and [2,8] (both contain 66). Remaining: [7,12], [10,16].

2.2. Arrow 22 at position 1212. Bursts [7,12] and [10,16] (both contain 1212). Remaining: none. Total arrows: 22. Notice [2,8] and [7,12] do not overlap (gap at 6-7), so they need separate arrows. The key is finding where one group ends and another begins. Each arrow represents a maximal group of overlapping balloons.