题目描述
力扣第452题
思路
区间合并是按左端点排序,在区间合并的过程中,每次扩展最大右端点,遍历区间时比较当前区间左端点和当前合并区间的右端点,小于等于则加入,并更新最大右端点。
区间选点需要考虑重叠区间,首先按左端点排序,在遍历过程中,不同于区间合并的扩展右端点,他需要不断紧缩右端点,这个右端点是重叠的区间。遍历区间时,如果当前区间左端点超出重叠区间右端点,则需要另外开辟新的“当前重叠区间”,即增加一个点。如果当前区间左端点小于等于重叠区间右端点,则该区间可以被重叠区间内的点选择,并且更新当前重叠区间的右端点。
C++ 代码
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
sort(points.begin(), points.end());
int ans = 0;
int ed = -1;
for(auto point : points){
if(ed == -1){
ed = point[1];
continue;
}
if(point[0] <= ed){
ed = min(ed, point[1]);
}else{
++ans;
ed = point[1];
}
}
++ans;
return ans;
}
};