Maximum Length Chain of Pairs | Set | C ++ implementation of the above approach ; Structure for storing pairs of first and second values . ; Comparator function which can compare the second element of structure used to sort pairs in increasing order of second value . ; Function for finding max length chain ; Initialize length l = 1 ; Sort all pair in increasing order according to second no of pair ; Pick up the first pair and assign the value of second element fo pair to a temporary variable s ; Iterate from second pair ( index of the second pair is 1 ) to the last pair ; If first of current pair is greater than previously selected pair then select current pair and update value of l and s ; Return maximum length ; Driver Code ; Declaration of array of structure ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct val { int first ; int second ; } ; bool comparator ( struct val p1 , struct val p2 ) { return ( p1 . second < p2 . second ) ; } int maxChainLen ( struct val p [ ] , int n ) { int l = 1 ; sort ( p , p + n , comparator ) ; int s = p [ 0 ] . second ; for ( int i = 1 ; i < n ; i ++ ) { if ( p [ i ] . first > s ) { l ++ ; s = p [ i ] . second ; } } return l ; } int main ( ) { val p [ ] = { { 5 , 24 } , { 39 , 60 } , { 15 , 28 } , { 27 , 40 } , { 50 , 90 } } ; int n = sizeof ( p ) / sizeof ( p [ 0 ] ) ; cout << maxChainLen ( p , n ) << endl ; return 0 ; }