Maximum length pair chain

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
28 upvotes
Asked in companies
UberMicrosoftAmazon

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
3
5 8 
3 4
3 4
2
2 3
-1 2
Sample Output 1:
2
1
Explanation for Sample Output 1:
In test case 1, The max length pair chain will be [3,4], -> [5,8] as 4 < 5 that means we can join these two pairs and form a chain of length two.

In test case 2, To join two pairs (a,b), (c,d) we need b < c but this condition is not satisfied by the given pairs in the input hence the max length will be 1 and the max length pair chain will be [2,3] or [-1,2].
Sample Input 2:
2
1
10 20
4
4 6
2 3
9 12
15 20
Sample Output 2:
1
4
Explanation for Sample Output 2:
In test case 1, The max length pair chain will be [10,20] form a chain of length one.

In test case 2, The max length pair chain will be [2,3] -> [4,6] -> [9,12] -> [15,20], that means we can join these two pairs as it satisfies the condition and form a chain of length four.
Hint

Try checking all the possible follow up pairs while forming a chain.

Approaches (4)
Brute Force

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.
Time Complexity

O(N ^ N), Where ‘N’ is the number of pairs.
 


Since we will have N ^ N nodes in the recursion tree. Thus the time complexity will be O(N ^ N).

Space Complexity

O(N), Where ‘N’ is the number of pairs.
 


Since the recursive function stack will contain ‘N’ elements. Thus the space complexity will be O(N).

Code Solution
(100% EXP penalty)
Maximum length pair chain
Full screen
Console