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 Function
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Pair { int a ; int b ; } ; int compare ( Pair x , Pair y ) { return x . a < y . a ; } void maxChainLength ( vector < Pair > arr ) { sort ( arr . begin ( ) , arr . end ( ) , compare ) ; vector < vector < Pair > > L ( arr . size ( ) ) ; L [ 0 ] . push_back ( arr [ 0 ] ) ; for ( int i = 1 ; i < arr . size ( ) ; i ++ ) { for ( int j = 0 ; j < i ; j ++ ) { if ( ( arr [ j ] . b < arr [ i ] . a ) && ( L [ j ] . size ( ) > L [ i ] . size ( ) ) ) L [ i ] = L [ j ] ; } L [ i ] . push_back ( arr [ i ] ) ; } vector < Pair > maxChain ; for ( vector < Pair > x : L ) if ( x . size ( ) > maxChain . size ( ) ) maxChain = x ; for ( Pair pair : maxChain ) cout << " ( " << pair . a << " , ▁ " << pair . b << " ) ▁ " ; } int main ( ) { Pair a [ ] = { { 5 , 29 } , { 39 , 40 } , { 15 , 28 } , { 27 , 40 } , { 50 , 90 } } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; vector < Pair > arr ( a , a + n ) ; maxChainLength ( arr ) ; return 0 ; }