119. Minimum Number of Arrows to Burst Balloons

Medium · Array

You are given an array of balloons represented by their horizontal positions as intervals [xstart, xend]. An arrow shot at position x bursts all balloons where xstart ≤ x ≤ xend. Find the minimum number of arrows needed to burst all balloons.

Note: You may assume that xstart ≤ xend for each balloon. Balloons may overlap, and an arrow can burst multiple balloons if it hits their overlapping region.

Examples

Example 1
Input: [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: One arrow at position 6 bursts balloons [2,8], [1,6], and [10,16] cannot be burst by this arrow. One arrow at position 11 bursts [10,16] and [7,12]. Total: 2 arrows.
Example 2
Input: [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: Each balloon is disjoint, so we need one arrow for each balloon.

Constraints