Print Maximum Length Chain of Pairs | Dynamic Programming solution to construct Maximum Length Chain of Pairs ; comparator function for sort function ; Function to construct Maximum Length Chain of Pairs ; Sort by start time ; L [ i ] stores maximum length of chain of arr [ 0. . i ] that ends with arr [ i ] . ; L [ 0 ] is equal to arr [ 0 ] ; start from index 1 ; for every j less than i ; L [ i ] = { Max ( L [ j ] ) } + arr [ i ] where j < i and arr [ j ] . b < arr [ i ] . a ; print max length vector ; Driver Code
class Pair : NEW_LINE INDENT def __init__ ( self , a , b ) : NEW_LINE INDENT self . a = a NEW_LINE self . b = b NEW_LINE DEDENT def __lt__ ( self , other ) : NEW_LINE INDENT return self . a < other . a NEW_LINE DEDENT DEDENT def maxChainLength ( arr ) : NEW_LINE INDENT arr . sort ( ) NEW_LINE L = [ [ ] for x in range ( len ( arr ) ) ] NEW_LINE L [ 0 ] . append ( arr [ 0 ] ) NEW_LINE for i in range ( 1 , len ( arr ) ) : NEW_LINE INDENT for j in range ( i ) : NEW_LINE INDENT if ( arr [ j ] . b < arr [ i ] . a and len ( L [ j ] ) > len ( L [ i ] ) ) : NEW_LINE INDENT L [ i ] = L [ j ] NEW_LINE DEDENT DEDENT L [ i ] . append ( arr [ i ] ) NEW_LINE DEDENT maxChain = [ ] NEW_LINE for x in L : NEW_LINE INDENT if len ( x ) > len ( maxChain ) : NEW_LINE INDENT maxChain = x NEW_LINE DEDENT DEDENT for pair in maxChain : NEW_LINE INDENT print ( " ( { a } , { b } ) " . format ( a = pair . a , b = pair . b ) , end = " ▁ " ) NEW_LINE DEDENT print ( ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ Pair ( 5 , 29 ) , Pair ( 39 , 40 ) , Pair ( 15 , 28 ) , Pair ( 27 , 40 ) , Pair ( 50 , 90 ) ] NEW_LINE n = len ( arr ) NEW_LINE maxChainLength ( arr ) NEW_LINE DEDENT