【leetcode】452. Minimum Number of Arrows to Burst Balloons(【leetcode】452. Minimum Number of Arrows to Burst Balloons)-其他

【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<b;}
class Solution {
public:

int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(),points.end(),cmp);
int res=1,end=points;
for(int i=1;i<points.size();++i){
if(points[i]<=end) {
end=min(end,points[i]);
}
else{
res++;
end=points[i];
}
}
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<b;}
class Solution {
public:

int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(),points.end(),cmp);
int res=1,end=points;
for(int i=1;i<points.size();++i){
if(points[i]<=end) {
end=min(end,points[i]);
}
else{
res++;
end=points[i];
}
}
return res;
}
};