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}热门推荐
10 香港老妈结婚祝福语简短
11 毕业立体贺卡祝福语简短
12 简短新年年会祝福语
13 评论小品祝福语大全简短
14 恭喜师兄结婚祝福语简短
15 员工集体辞职祝福语简短
16 高中新生祝福语 简短
17 装修祝福语男生搞笑简短
18 生日开业蛋糕祝福语简短