資料結構
網路
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 個瀏覽量
廣告