85. Minimum Number of Arrows to Burst Balloons

Balloons are on a 2D plane as points[i]=[x_start,x_end]. An arrow shot at x bursts all balloons where x_start<=x<=x_end. Return minimum arrows to burst all balloons.

Input: 2D array points where points[i]=[x_start, x_end].

Output: Minimum number of arrows.

Examples

Input: [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: Shoot at 6 and 11.

Input: [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: No overlaps.

Input: [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Explanation: Shoot at 2 and 4.

Constraints

• 1<=points.length<=10^5
• -2^31<=x_start<=x_end<=2^31-1

Asked by