Maximal Disjoint Intervals | C ++ implementation of the approach ; Function to sort the vector elements by second element of pairs ; Function to find maximal disjoint set ; Sort the list of intervals ; First Interval will always be included in set ; End point of first interval ; Check if given interval overlap with previously included interval , if not then include this interval and update the end point of last added interval ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long int NEW_LINE bool sortbysec ( const pair < int , int > & a , const pair < int , int > & b ) { return ( a . second < b . second ) ; } void maxDisjointIntervals ( vector < pair < int , int > > list ) { sort ( list . begin ( ) , list . end ( ) , sortbysec ) ; cout << " [ " << list [ 0 ] . first << " , ▁ " << list [ 0 ] . second << " ] " << endl ; int r1 = list [ 0 ] . second ; for ( int i = 1 ; i < list . size ( ) ; i ++ ) { int l1 = list [ i ] . first ; int r2 = list [ i ] . second ; if ( l1 > r1 ) { cout << " [ " << l1 << " , ▁ " << r2 << " ] " << endl ; r1 = r2 ; } } } int main ( ) { int N = 4 ; vector < pair < int , int > > intervals = { { 1 , 4 } , { 2 , 3 } , { 4 , 6 } , { 8 , 9 } } ; maxDisjointIntervals ( intervals ) ; return 0 ; }