Maximum length of chain pairs

In the given n pairs of numbers, find the longest chain in which (c, d) can follow (a, b) if b < c.

In the given pairs first element is always smaller than the second.

Example

Input : [{12, 14}, {23, 29}, {18, 41}, {30,34}]
Output : 3

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

Algorithm

Time complexity: O(n)

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

b. Here we use modified LIS,
    1) Compare the first element of current and second element of chain created.
    2) If no pairs in chain add the first pair.
    3) If first element > second element of last in chain add element.
    4) Else, replace.

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

Algorithm working

C++ Program

#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;
}
Try It


Next > < Prev
Scroll to Top