Maximum Length of Chain
Last Updated: 4 Jan, 2021
Difficulty: Moderate
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”.
Approach 2
After observing approach 1 we can find that there are some redundant function calls which means that there are some overlapping subproblems. The repetition of such sub-problems suggests that we can use dynamic programming to optimize our approach.
The key idea behind a dynamic programming approach is to use memoization, i.e. we’ll save the result of our sub-problem in a matrix so that it can be used later on.
Let dp[ i ] be our dynamic programming array to store the length of the longest chain ending at ith pair.
Now consider the following implementation of getLength(int i) using memoization.
- Before calling the function for any valid ‘i’, we will first check whether we already have a solution corresponding to the ‘i’ if it is, then returns the answer from the “dp” array.
- If (i == 0) then return 1 because a single pair will make a chain of length one.
- Otherwise, initialize a variable “ans” to zero which stores the length of the longest chain ending at pairs[j] 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) )
- Store the “ans” in the “dp” array for later use.
Approach 3
The basic idea here is to use a bottom-up dynamic programming approach to solve the problem. The recursion function is discussed in the above-mentioned approach.
Let dp[ i ] be our dynamic programming array to store the length of the longest chain ending at ith pair.
Now, consider the following steps :
- Initialize the “dp” with 1 because each pair can be treated as a chain of length one.
- Start traversing the given string using a variable ‘i’
- Create a nested loop using a variable ‘j’ such that 0 <= j < i
- If pairs[i][0] > pairs[j][1] then update dp[i] = max(dp[i], dp[j] + 1)
- Create a nested loop using a variable ‘j’ such that 0 <= j < i
- The maximum value in the “dp” array will be the length of the longest chain. Because the longest chain will necessarily end on some index.
Approach 4
The basic idea of this approach is to greedily add pairs to the chain. We can observe that the chain will always be sorted by the second integer in increasing order.
Why??
Because the first integer of any pair will be greater than the second integer of the previous one. And since it is given that the first integer in any pair is always less than the second one. So, the second integer will always be greater than the second integer of the previous pair.
Now our strategy is to choose the next valid pair with the minimum second integer.
Let us try to prove the above-mentioned greedy strategy always gives the optimal result.
Suppose we currently have a chain of ‘K’ length and the last pair in the chain is (a, b).
Now assume that we are not choosing the pair with a minimum second integer, let say the chosen pair is (c, d) where c > b. Now there must exist a pair (e, f) such that e > a and f < d.
Since we have already shown that the chain will be sorted by its second element in increasing order. So the pair (e, f) can never be added to the chain again. So, it is always better to choose the next valid pair with the minimum second integer.
Now, consider the following steps:
- Sort the given pairs by their second integer in non-decreasing order. Initialize a variable “maxLength” to zero which stores the length of the longest chain possible. Also, initialize a variable “previous” to INT_MIN which
- Start traversing the array/list of pairs.
- Increment “maxLength” by one, if the first element of the current pair is greater than “previous”. And update the “previous” with the second element of the current pair.
