資料結構
網路
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 次
廣告