Maximum Length of Chain
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.
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.
You are not required to print the expected output; it has already been taken care of. Just implement the function.
1 <= T <= 50 1 <= N <= 1000 0 <= pairs[i], pairs[i] <= 10^6 Time limit: 1 sec
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
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] > pairs[j]. 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] > pairs[j] ) holds true.
Now, consider the following steps to implement getLength(i) :