C++での最大の互いに素な間隔

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}