数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++程序：查找需要移除的最小区间数以消除重叠
假设我们有一组区间；我们必须找到应移除的最小区间数，以使其余区间不重叠。例如，如果区间是[[8,10],[3,5],[6,9]]，则输出为1，因为我们必须移除[6,9]才能使其他区间不重叠。
为了解决这个问题，我们将遵循以下步骤：
- n := 数组大小
- 如果n为0，则返回0
- count := 1
- 根据区间的结束时间对数组进行排序
- end := 第一个区间的结束日期
- 对于范围1到n – 1中的i
- 如果arr[i]的开始时间 >= end，则
- end := arr[i]的结束时间
- 将count加1
- 如果arr[i]的开始时间 >= end，则
- 返回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 = {{8,10},{3,5},{6,9}};
Solution ob;
cout << (ob.eraseOverlapIntervals(v));
}输入
{{8,10},{3,5},{6,9}}输出
1
更新于：2020年10月20日
413 次浏览
广告