資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的非重疊區間
假設我們有一組區間；我們必須找出需要刪除的最小區間數以使其餘區間不重疊。因此，如果區間為 [[1,2], [2,3], [3,4], [1,3]]，則輸出將為 1，因為我們必須刪除 [1,3] 使所有其他區間不重疊。
為了解決這個問題，我們將遵循以下步驟 −
n := 陣列大小
如果 n 為 0，則返回 0
count := 1
根據區間結束時間對陣列進行排序
end :=第一個區間的的結束時間
對於 i 在 1 到 n – 1 的範圍內
如果 arr[i] 的開始時間 >= end，則
end := arr[i] 的結束時間
count 增加 1
返回 n – count
讓我們看看以下實現以獲得更好的理解 −
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
static bool cmp(vector <int>& a, vector <int>& b){
return a[1] < b[1];
}
int eraseOverlapIntervals(vector<vector<int>>& arr) {
int n = arr.size();
if(!n)return 0;
int cnt = 1;
sort(arr.begin(), arr.end(), cmp);
int end = arr[0][1];
for(int i = 1; i < n; i++){
if(arr[i][0] >= end){
end = arr[i][1];
cnt++;
}
}
return n - cnt;
}
};
main(){
vector<vector<int>> v = {{1,2},{1,2},{1,2}};
Solution ob;
cout << (ob.eraseOverlapIntervals(v));
}輸入
[[1,2],[1,2],[1,2]]
輸出
2
更新時間：30-Apr-2020
511 次瀏覽
廣告