Problem title
Difficulty
Avg time to solve

Distinct Paths
Moderate
20 mins
Sorting Of A Rotated Sorted Array
Easy
10 mins
Longest Common Subsequence
Moderate
--
Sub-Matrix with Sum Zero
Moderate
35 mins
Maximum Length of Chain
Moderate
15 mins
3 Divisors
Moderate
25 mins
Angle Between Hour Hand And Minute Hand
Easy
15 mins
Remove maximum edges
Easy
15 mins
Sorted Subsequence of Size 3
Moderate
15 mins
Check Square
Moderate
10 mins
2

Maximum Length of Chain

Difficulty: MEDIUM
Contributed By
Avg. time to solve
15 min
Success Rate
85%

Problem Statement

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
Sample Input 1 :
2
2
3 6
4 5
2
2 4
6 9
Sample output 1 :
1
2
Explanation For Sample output 1 :
For the first test case, one of the longest chains is (3, 6) of length 1.

For the second test case, the longest chain is (2, 4) -> (6, 9) and its length is 2.
Sample Input 2 :
2
3
1 2
2 3
3 4
1
7 8
Sample output 2 :
2
1
Reset Code
Full screen
copy-code
Console