C ++中移除被覆盖的间隔
假设我们有一个间隔列表，我们必须删除列表中另一个间隔覆盖的所有间隔。在且仅当c<=a和b<=d时，间隔[a，b）才由间隔[c，d）覆盖。因此，这样做之后，我们必须返回剩余间隔的数量。如果输入类似于[[1,4]，[3,6]，[2,8]]，则输出为2，间隔[3,6]由[1,4]和[2覆盖，8]，因此输出为2。
为了解决这个问题，我们将遵循以下步骤-
根据结束时间对间隔列表进行排序
定义一个堆栈st
当我的范围是0到a–1的大小时
temp：=a[i]
当st不为空且temp和stacktop间隔相交时
将temp插入st
从堆栈弹出
将a[i]插入st
如果堆栈为空或a[i]并且堆栈顶部间隔相交，
除此以外
st的返回大小。
例子（C++）
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool intersect(vector <int>& a, vector <int>& b){
return (b[0] <= a[0] && b[1] >= a[1]) || (a[0] <= b[0] && a[1] >= b[1]);
}
static bool cmp(vector <int> a, vector <int> b){
return a[1] < b[1];
}
void printVector(vector < vector <int> > a){
for(int i = 0; i < a.size(); i++){
cout << a[i][0] << " " << a[i][1] << endl;
}
cout << endl;
}
int removeCoveredIntervals(vector<vector<int>>& a) {
sort(a.begin(), a.end(), cmp);
stack < vector <int> > st;
for(int i = 0; i < a.size(); i++){
if(st.empty() || !intersect(a[i], st.top())){
st.push(a[i]);
}
else{
vector <int> temp = a[i];
while(!st.empty() && intersect(temp, st.top())){
st.pop();
}
st.push(temp);
}
}
return st.size();
}
};
main(){
vector<vector<int>> v = {{1,4},{3,6},{2,8}};
Solution ob;
cout << (ob.removeCoveredIntervals(v));
}输入项
[[1,4],[3,6],[2,8]]
输出结果
2