Greedy Algorithms8 sections · 316 units
Open in Course

Problem - Minimum Number of Arrows

Burst all balloons

Balloons are represented as intervals on the x-axis. An arrow shot at position xx bursts all balloons where xstartxxendx_{start} \leq x \leq x_{end}.

Find the minimum number of arrows to burst all balloons. For balloons [[10,16],[2,8],[1,6],[7,12]][[10,16],[2,8],[1,6],[7,12]], answer is 22. One arrow at x=6x=6 bursts [2,8][2,8] and [1,6][1,6].

Another at x=11x=11 bursts [10,16][10,16] and [7,12][7,12]. Tricky: overlapping balloons can be burst by the same arrow. Sorting by end point ensures you process balloons in optimal order.