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}