Maximal Disjoint Intervals | 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
def maxDisjointIntervals ( list_ ) : NEW_LINE INDENT list_ . sort ( key = lambda x : x [ 1 ] ) NEW_LINE print ( " [ " , list_ [ 0 ] [ 0 ] , " , ▁ " , list_ [ 0 ] [ 1 ] , " ] " ) NEW_LINE r1 = list_ [ 0 ] [ 1 ] NEW_LINE for i in range ( 1 , len ( list_ ) ) : NEW_LINE INDENT l1 = list_ [ i ] [ 0 ] NEW_LINE r2 = list_ [ i ] [ 1 ] NEW_LINE if l1 > r1 : NEW_LINE INDENT print ( " [ " , l1 , " , ▁ " , r2 , " ] " ) NEW_LINE r1 = r2 NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 4 NEW_LINE intervals = [ [ 1 , 4 ] , [ 2 , 3 ] , [ 4 , 6 ] , [ 8 , 9 ] ] NEW_LINE maxDisjointIntervals ( intervals ) NEW_LINE DEDENT