数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会科学
时尚研究
法律研究C++ 中的最大不相交区间
描述
给定一组 N 个区间，任务是找到最多不相交区间的集合。如果两个区间 [i, j] 和 [k,l] 在任何点都没有公共点，则称它们不相交
如果区间为 {{10, 20} {23, 35}, {15, 21}, {37, 41}}，则最大不相交非重叠对为 -
{10, 20}
{23, 35}
{37, 41}请注意，我们不能包含 {15, 21}，因为它将与 {10, 20} 重叠
算法
1. Sort the intervals, with respect to their end points. 2. Traverse the all intervals, if we get two overlapping intervals, then choose the interval with lower end point. Choosing such interval will ensure that intervals further can be accommodated without any overlap 3. Repeat the same procedure for all the intervals and print all the intervals which satisfy these criteria
示例
#include <bits/stdc++.h>
using namespace std;
bool sortFun(pair<int, int> &a, pair<int, int> &b){
return (a.second < b.second);
}
void getMaxDisjointInterval(vector<pair<int, int>> intervals){
sort(intervals.begin(), intervals.end(), sortFun);
cout << "{" << intervals[0].first << ", " << intervals[0].second << "}\n";
int r1 = intervals[0].second;
for (int i = 1; i < intervals.size(); ++i) {
int l1 = intervals[i].first;
int r2 = intervals[i].second;
if (l1 > r1) {
cout << "{" << l1 << ", " << r2 << "}\n";
r1 = r2;
}
}
}
int main(){
int n = 4;
vector<pair<int, int>> intervals = {
{10, 20},
{23, 35},
{15, 21},
{37, 41}
};
cout << "Max disjoint pairs are:\n";
getMaxDisjointInterval(intervals);
return 0;
}输出
当您编译并执行以上程序时，它将生成以下输出 -
Max disjoint pairs are:
{10, 20}
{23, 35}
{37, 41}
更新于：2019 年 12 月 24 日
228 个浏览量
广告