数据结构
网络
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 次浏览
广告