贪心
1、先按照所有起球的右边界排序,记录第一个气球的右边界位置,如果后续气球的左边界小于记录中的值那么这个气球就是可以被箭射中的,这种情况不做处理。
2、当出现遍历的时候某一个起球的左边界大于当前记录中的值的时候,那么此时第一个箭就射不中当前的气球了,所以箭的数量++,并且记录中的值等于当前遍历气球的有边界,(箭的下标在保证原本应该被射爆的气球还是被射爆的情况下尽可能的往右取,这个值被右下标最小的气球所限制),
3、还有一种情况是,当出现左下边不满足小于记录值的情况箭的数量就++,那么之后再出现后面的气球满足之前的记录值的情况怎么办,这种情况解释为,能被之前的记录的箭所射爆的气球,也一定能被更新之后的箭所射爆(具体解释看官方题解)
第三种情况的图例
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
if(points.empty()){
return 0;
}
sort(points.begin(),points.end(),[](const vector<int>& a,const vector<int>& b){
return a[1]<b[1];
});
int pos = points[0][1];//最小的有边界
int ans = 1;
for(const vector<int>& ballon:points){
if(ballon[0]>pos){
pos = ballon[1];
++ans;
}
}
return ans;
}
};
标签:return,边界,ballon,记录,452,气球,points,LeetCode
From: https://www.cnblogs.com/poteitoutou/p/16877453.html