## 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;
}
```