Minimum Number of Arrows to Burst Balloons

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [x_start, x_end].

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with x_start and x_end is burst by an arrow shot at x if x_start <= x <= x_end.

Return the minimum number of arrows that must be shot to burst all balloons.

Examples

Input: points = [[10,16],[2,8],[1,6],[7,12]]

Output: 2

Shoot one arrow at x = 6 (bursting [2,8] and [1,6]) and another at x = 11 (bursting [10,16] and [7,12]).

Constraints

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

Complexity Analysis

Time

O(N log N)

due to sorting the balloons.

Space

O(1) auxiliary space.

Test Cases

#1 Overlap handled

Input: points = [[10,16],[2,8],[1,6],[7,12]]

Expected: 2

#2 No overlap

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

Expected: 4