Minimum Number of Arrows to Burst Balloons

Medium

There are some spherical balloons taped onto a flat wall. The balloons are given as a 2D array points where points[i] = [xstart, xend] is the horizontal span of the i-th balloon.

Arrows are shot vertically upward from a point x on the x-axis. A balloon with span [xstart, xend] is burst if xstart <= x <= xend. An arrow travels infinitely upward, bursting every balloon it passes through.

Return the minimum number of arrows that must be shot to burst all balloons. On this judge the array is passed as a grid with two columns.

Example 1

Input:  grid = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: Shoot at x = 6 to burst [2,8] and [1,6], then at x = 11 to burst [10,16] and [7,12].

Example 2

Input:  grid = [[1,2],[3,4],[5,6],[7,8]]
Output: 4

Example 3

Input:  grid = [[1,2],[2,3],[3,4],[4,5]]
Output: 2

Constraints

• 1 <= points.length <= 10^5
• points[i].length == 2
• -2^31 <= xstart < xend <= 2^31 - 1