Maximum length pair chain

Posted: 25 Dec, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given ‘N’ pairs of integers in which the first number is always smaller than the second number i.e in pair (a,b) -> a < b always. Now we define a pair chain as the continuous arrangement of pairs in which a pair (c,d) can follow another pair (a,b) only when b < c.

Find the length of the longest pair chain that can be formed using the given pairs.

Example:
Given Pairs =  [3,4], [1,2], [2,3].

The length of the maximum chain will be 2. The longest chain is [1,2] -> [3,4].
Note:
1. You can select a pair only once.

2. You needn’t use up all the given pairs.

3. You can select pairs in any order. 
Input Format:
The first line of the input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains a single positive integer ‘N’ denoting the total number of the pairs.

Next ‘N’ lines of each test case contain two space-separated integers ‘a’ and ‘b’ denoting the elements of the pair.
Output Format:
For each test case, return a positive integer denoting the maximum length of the pair chain that can be possible while satisfying the given condition.

The output of each test case will be printed in a separate line.
Note:
You don’t need to print anything, it has been already taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N <= 10^4 
-10^9 <= a,b <= 10^9

Where ‘a’ and ‘b’ is the elements of the pair.

Time Limit: 1 sec
Approach 1

We will solve this problem recursively by dividing it into subproblems. We first need to sort the array according to their first element. But why? as it is given in the question that you can pick any pair in any order so if you pick a pair at index ‘i’ then for the next pair you need to try all pairs from [0, ‘N’ - 1] which are not selected in the current chain that will make our implementation more difficult. So with the help of sorting the array, we ensure that our next pair will always lie after the chosen index ‘i’.

 

After the sorting, for each pair we have two choices: either we can include this pair in our current chain or do not include this pair in our current chain.

 

  • If we do not include this pair in our current chain then we can simply skip this pair and recur for the next pair present on index ‘i' +1.
  • If we include this pair in our current chain then we increment our length by 1 and recur on the next possible pair which satisfies the condition that the next pair should have its first element greater than the second element of the current pair.
  • Also, we already sort the array so we know the next possible pair will lie after the current pair i.e, if the index of the current pair is ‘i’ then we will recur in the range ['i' + 1, ‘N’ - 1] for the next possible pair.
  • At each step, we will take the maximum length which we can get by the above two choices for the current pair.
Try Problem