Dynamic Programming | Set 20 (Maximum Length Chain of Pairs) | GeeksforGeeks

LeetCode 646 - Maximum Length of Pair Chain
Dynamic Programming | Set 20 (Maximum Length Chain of Pairs) | GeeksforGeeks
You are given n pairs of numbers. In every pair, the first number is always smaller than the second number. A pair (c, d) can follow another pair (a, b) if b < c. Chain of pairs can be formed in this fashion. Find the longest chain which can be formed from a given set of pairs.

For example, if the given pairs are {{5, 24}, {39, 60}, {15, 28}, {27, 40}, {50, 90} }, then the longest chain that can be formed is of length 3, and the chain is {{5, 24}, {27, 40}, {50, 90}}

Time Complexity: O(n^2) where n is the number of pairs.

This problem is a variation of standard Longest Increasing Subsequence problem. 
1) Sort given pairs in increasing order of first (or smaller) element.
2) Now run a modified LIS process where we compare the second element of already finalized LIS with the first element of new LIS being constructed.

// This function assumes that arr[] is sorted in increasing order

// according the first (or smaller) values in pairs.

int maxChainLength( struct pair arr[], int n)

{

   int i, j, max = 0;

   int *mcl = (int*) malloc ( sizeof( int ) * n );

   /* Initialize MCL (max chain length) values for all indexes */

   for ( i = 0; i < n; i++ )

      mcl[i] = 1;

   /* Compute optimized chain length values in bottom up manner */

   for ( i = 1; i < n; i++ )

      for ( j = 0; j < i; j++ )

         if ( arr[i].a > arr[j].b && mcl[i] < mcl[j] + 1)

            mcl[i] = mcl[j] + 1;

   // mcl[i] now stores the maximum chain length ending with pair i

   /* Pick maximum of all MCL values */

   for ( i = 0; i < n; i++ )

      if ( max < mcl[i] )

         max = mcl[i];

   /* Free memory to avoid memory leak */

   free( mcl );

   return max;

}

The given problem is also a variation of Activity Selection problem and can be solved in (nLogn) time. To solve it as a activity selection problem, consider the first element of a pair as start time in activity selection problem, and the second element of pair as end time. Thanks to Palash for suggesting this approach.

http://www.geeksforgeeks.org/print-maximum-length-chain-of-pairs/

struct Pair

{

    int a;

    int b;

};

// comparator function for sort function

int compare(Pair x, Pair y)

{

    return x.a < y.a;

}

// Function to construct Maximum Length Chain

// of Pairs

void maxChainLength(vector<Pair> arr)

{

    // Sort by start time

    sort(arr.begin(), arr.end(), compare);

    // L[i] stores maximum length of chain of

    // arr[0..i] that ends with arr[i].

    vector<vector<Pair> > L(arr.size());

    // L[0] is equal to arr[0]

    L[0].push_back(arr[0]);

    // start from index 1

    for (int i = 1; i < arr.size(); i++)

    {

        // for every j less than i

        for (int j = 0; j < i; j++)

        {

            // L[i] = {Max(L[j])} + arr[i]

            // where j < i and arr[j].b < arr[i].a

            if ((arr[j].b < arr[i].a) &&

                (L[j].size() > L[i].size()))

                L[i] = L[j];

        }

        L[i].push_back(arr[i]);

    }

    // print max length vector

    vector<Pair> maxChain;

    for (vector<Pair> x : L)

        if (x.size() > maxChain.size())

            maxChain = x;

    for (Pair pair : maxChain)

        cout << "(" << pair.a << ", "

             << pair.b << ") ";

}

Read full article from Dynamic Programming | Set 20 (Maximum Length Chain of Pairs) | GeeksforGeeks