数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时装研究
法律研究在 C++ 中删除重叠区间
假设我们有一个区间列表，我们必须删除列表中被另一个区间覆盖的所有区间。如果且仅当 c <= a 且 b <= d，则区间 [a,b) 被区间 [c,d) 覆盖。因此，在这样做之后，我们必须返回剩余区间的数量。如果输入为 [[1,4],[3,6],[2,8]]，那么输出将为 2，区间 [3,6] 被 [1,4] 和 [2,8] 覆盖，所以输出将为 2。
为了解决这个问题，我们将遵循以下步骤：
- 根据结束时间对区间列表进行排序
- 定义一个栈 st
- i 的范围是从 0 到 a 的大小 - 1
- 如果栈为空或 a[i] 和栈顶区间相交，
- 把 a[i] 插入 st
- 否则
- temp := a[i]
- 当 st 不为空且 temp 和栈顶区间相交时
- 从栈中弹出
- 把 temp 插入 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
更新日期：30-Apr-2020
已浏览 242 次
广告