Minimum Arrows to Burst Balloons
Problem statement
Balloons are fixed along a wall. Balloon i covers every horizontal position from balloons[i][0] to balloons[i][1], ends included.
An arrow shot straight up from position x bursts every balloon whose span contains x; it keeps flying, so one arrow can burst many balloons. Return the fewest arrows that burst every balloon.
Function
minArrows(balloons: int[][]) → intExamples
Example 1
balloons = [[3,9],[1,4],[7,12],[10,11]]return = 2An arrow at 4 bursts [1, 4] and [3, 9]. An arrow at 11 bursts [7, 12] and [10, 11]. One arrow cannot do it: [1, 4] and [10, 11] share no position.
Example 2
balloons = [[0,2],[2,4],[5,5]]return = 2[0, 2] and [2, 4] touch at 2, so one arrow at 2 bursts both. [5, 5] needs its own arrow at 5.
Example 3
balloons = [[1,10],[2,3],[5,6]]return = 2[2, 3] and [5, 6] share no position, so at least two arrows are needed. Arrows at 3 and 6 work, and the wide balloon [1, 10] is burst by either.
Constraints
1 <= balloons.length <= 2000- each
balloons[i] = [start, end]with-2^31 <= start <= end <= 2^31 - 1