Maximum Length of Chain Pairs

Problem Statement

In the maximum length of chain pairs problem we have given n pairs of numbers, find the longest chain in which (c, d) can follow (a, b) if b < c. In the given pairs the first element is always smaller than the second.

 Example

Input

[{12, 14}, {23, 29}, {18, 41}, {30,34}]

Output

3

Explanation

Here, chain is {12, 14}, {23, 29}, {30, 34}

Approach for Maximum Length of Chain Pairs

Here we use the modified way of the longest increasing subsequence algorithm. First, we need to sort the elements such a way that the first element is always in the increasing order. Now we apply the longest increasing subsequence to the current pair of the vector. Now, compare the first element of the current and second element of the chain created. If no pairs in chain add the first pair. If the first element > second element of last in chain add an element. Else, replace. Now for more understanding see the step by step execution of the logic-

arr[] = { {12, 14}, {23, 29}, {18, 41}, {30,34} };

First, we sort the array on the basis of the first element.

arr[]  = { {12,14}, {18,41}, {23,29}, {30,34} }

Now add the elements to the chain and increase the counts of the length.

chain = { {12,14} }; //step 1;

chain = { {12,14}, {23,29}}; // step 2;

chain = { {12,14}, {23,29}, {30,34}}; //step 3;

Algorithm

a. Sort the given pairs according, to the first element increasing order.

b. Here we use modified LIS,

• Compare the first element of the current and second element of the chain created.
• If no pairs in chain add the first pair.
• If the first element > second element of last in chain add an element.
• Else, replace.

c. Finally, return the length of the chain created.

Implementation

C++ Program for Maximum Length of Chain Pairs

#include <stdio.h>
#include <stdlib.h>
//pair structure
struct pair
{
  int a;
  int b;
};
 
int MaxChainLen(struct pair array[], int n)
{
   int i, j, maximum_len = 0;
   int *length_array = (int*) malloc ( sizeof( int ) * n );
   //initilize length array
   for ( i = 0; i < n; i++ )
   {
      length_array[i] = 1;
   }
   //algorithm
   for(i = 1; i < n; i++ ){
      for(j = 0; j < i; j++ )
      {
         if(array[i].a > array[j].b && length_array[i] < length_array[j] + 1)
         {
            length_array[i] = length_array[j] + 1;
         }
        }
   }
   for(i = 0; i < n; i++ )
   {
      if(maximum_len < length_array[i] )
       { 
         maximum_len = length_array[i];
       }
   }
   free( length_array );
   return maximum_len;
}
 
/* Driver program to test above function */
int main()
{
    struct pair input_array[] = {{12, 14}, {18, 41}, {23, 29}, {30, 34}};
    int size = sizeof(input_array)/sizeof(input_array[0]);
    printf("length of longest chain is: %d",MaxChainLen(input_array,size));
    return 0;
}

import java.util.Scanner;
class sum
{
    public static int MaxChainLen(int array[][], int n)
    {
       int i, j, maximum_len = 0;
       int length_array[] = new int[n];
       //initilize length array
       for ( i = 0; i < n; i++ )
       {
          length_array[i] = 1;
       }
       //algorithm
       for(i = 1; i < n; i++ ){
          for(j = 0; j < i; j++ )
          {
             if((array[i][0] > array[j][1]) && (length_array[i] < (length_array[j] + 1)))
             {
                length_array[i] = length_array[j] + 1;
             }
            }
       }
       for(i = 0; i < n; i++ )
       {
          if(maximum_len < length_array[i] )
           { 
             maximum_len = length_array[i];
           }
       }
       return maximum_len;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[][] = new int[n][2];
        for(int i=0;i<n;i++)
        {
            arr[i][0] = sr.nextInt();
            arr[i][1] = sr.nextInt();
        } 
        int ans = MaxChainLen(arr,n);
        System.out.println("length of longest chain is: " + ans);
    } 
}

4
12 14 
18 41 
23 29 
30 34

length of longest chain is: 3