这道题同样使用贪心算法,和435是同一类型问题,这里需要求解不相交区间个数。
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(),points.end(),comp);
int size = points.size(),ans = 1;
if(size <= 0) return 0;
vector<int> x = points[0];
for(int i = 1;i < size;i++)
{
//计算不相交区间个数
if(points[i][0] > x[1])
{
ans++;
x = points[i];
}
}
return ans;
}
private:
static bool comp(const vector<int> &a,const vector<int> &b) {
return a[1] < b[1];
}
};