Maximal Disjoint Intervals | Java 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
import java . util . * ; class GFG { static class Pair implements Comparable < Pair > { int first , second ; Pair ( int f , int s ) { first = f ; second = s ; } @ Override public int compareTo ( Pair o ) { if ( this . second > o . second ) return 1 ; else if ( this . second == o . second ) return 0 ; return - 1 ; } } static void maxDisjointIntervals ( Pair [ ] list ) { Collections . sort ( Arrays . asList ( list ) ) ; System . out . print ( " [ " + list [ 0 ] . first + " , ▁ " + list [ 0 ] . second + " ] " + "NEW_LINE"); int r1 = list [ 0 ] . second ; for ( int i = 1 ; i < list . length ; i ++ ) { int l1 = list [ i ] . first ; int r2 = list [ i ] . second ; if ( l1 > r1 ) { System . out . print ( " [ " + l1 + " , ▁ " + r2 + " ] " + "NEW_LINE"); r1 = r2 ; } } } public static void main ( String [ ] args ) { int N = 4 ; Pair [ ] intervals = { new Pair ( 1 , 4 ) , new Pair ( 2 , 3 ) , new Pair ( 4 , 6 ) , new Pair ( 8 , 9 ) } ; maxDisjointIntervals ( intervals ) ; } }