There are several balloon intervals on a number line. Each balloon is represented as [start, end]. A vertical arrow shot at x bursts every balloon whose interval contains x. Return the minimum number of arrows needed to burst all balloons. Pattern focus: Interval Scheduling. Sort by end coordinate and always shoot the next arrow at the earliest finishing balloon that has not yet been burst.
points = balloon intervals [start, end]
minimum arrows required
Example 1:
Input:
points = [[10,16],[2,8],[1,6],[7,12]]
Output:
2
Explanation:
One arrow can burst the overlapping [1,6] and [2,8], and another can burst [7,12] and [10,16].
Example 2:
Input:
points = [[1,2],[3,4],[5,6],[7,8]]
Output:
4
Explanation:
No two balloons overlap, so each balloon needs its own arrow.
Example 3:
Input:
points = [[1,2],[2,3],[3,4],[4,5]]
Output:
2
Explanation:
An arrow at x=2 bursts the first two, and an arrow at x=4 bursts the last two.