Maximal Disjoint Intervals in C++

Description

Given a set of N intervals, the task is to find the maximal set of mutually disjoint intervals. Two intervals [i, j] & [k,l] are said to be disjoint if they do not have any point in common

If intervals are {{10, 20} {23, 35}, {15, 21}, {37, 41}} then maximum non-overlapping disjoint pairs are −

{10, 20}
{23, 35}
{37, 41}

Note that we cannot include {15, 21} as it will overlap with {10, 20}

Algorithm

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

Example

 Live Demo

#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;
}

Output

When you compile and execute the above program. It generates the following output −

Max disjoint pairs are:
{10, 20}
{23, 35}
{37, 41}