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}