【leetcode】452. Minimum Number of Arrows to Burst Balloons(【leetcode】452. 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  where  denotes a balloon whose horizontal diameter stretches between  and . You do not know the exact y-coordinates of the balloons.

points
points[i] = [xstart, xend]
xstart
xend

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with  and  is burst by an arrow shot at  if . There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

xstart
xend
x
xstart <= x <= xend

Given the array , return the minimum number of arrows that must be shot to burst all balloons.

points

Example 1:

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
- Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].

Example 2:

Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows.
bool cmp(vector<int>&a,vector<int>&b){return a[1]<b[1];}
class Solution {
public:
   
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(),points.end(),cmp);
        int res=1,end=points[0][1];
        for(int i=1;i<points.size();++i){
            if(points[i][0]<=end) {
                end=min(end,points[i][1]);
            }
            else{
                res++;
                end=points[i][1];
            }
        }
        return res;
    }
};
————————

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array  where  denotes a balloon whose horizontal diameter stretches between  and . You do not know the exact y-coordinates of the balloons.

points
points[i] = [xstart, xend]
xstart
xend

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with  and  is burst by an arrow shot at  if . There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

xstart
xend
x
xstart <= x <= xend

Given the array , return the minimum number of arrows that must be shot to burst all balloons.

points

Example 1:

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
- Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].

Example 2:

Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows.
bool cmp(vector<int>&a,vector<int>&b){return a[1]<b[1];}
class Solution {
public:
   
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(),points.end(),cmp);
        int res=1,end=points[0][1];
        for(int i=1;i<points.size();++i){
            if(points[i][0]<=end) {
                end=min(end,points[i][1]);
            }
            else{
                res++;
                end=points[i][1];
            }
        }
        return res;
    }
};