Maximum Length of Chain

Posted: 4 Jan, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You have been given an array/list “pairs” of ‘N’ pairs of integers. In every pair, the first number is always smaller than the second number. A pair (a, b) can follow another pair (c, d) in a chain if a > d. Now you are supposed to find the length of the longest chain which can be formed.

You can select pairs in any order.

Input Format :
The first line contains an integer ‘T’ denoting the number of test cases. Then each test case is as follows.

The first input line of each test case contains an integer ‘N’ which denotes the number of pairs.

Next ‘N’ lines contain two space-separated integers denoting a pair.
Output Format :
For each test case, print the length of the longest chain which can be formed.

Print the output of each test case in a separate line.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 50
1 <= N <= 1000 
0 <= pairs[i][0], pairs[i][1] <= 10^6

Time limit: 1 sec
Approach 1

The basic idea of this approach is to break the original problem into sub-problems. Let us sort the array/list of pairs by the first integer in non-decreasing order and define a recursive function 

 

getLength(int i)

 

Which returns the length of the longest chain which ends at pairs[i]. As per given in the problem statement pair[i] can follow a pair[j] (for any integer ‘j’) if pairs[i][0] > pairs[j][1]. Since the array/list is sorted in nondecreasing order and also it is given that the second integer is always greater than the first integer in any pair, ‘j’ must be less than ‘i’. 

 

Therefore, we can define getLength(i) = max(getLength(i), getLength(j) + 1) if j < i and ( pairs[i][0] > pairs[j][1] ) holds true.

 

Now, consider the following steps to implement getLength(i) :

 

  • If (i == 0) then return 1 because a single pair will make a chain of length one.
  • Otherwise, initialize a variable “ans” to one which stores the length of the longest chain ending at pairs[i] start traversing the array/list using a variable ‘j’ such that ‘j’ < ‘i’
    • If pairs[i][0] > pairs[j][1] then update ans = max(ans, 1 + getLength(j) )
  • Return “ans”.
Try Problem