New update is available. Click here to update.
sidenav-btnClose
Topic list
Maximum Length of Chain
MEDIUM
15 mins
2 upvotes
Dynamic Programming
Topics (Covered in this problem)
Problem solved
Skill meter
Dynamic Programming
-
Other topics
Problem solved
Skill meter
Strings
-
Matrices (2D Arrays)
-
Sorting
-
Binary Search
-
Linked List
-
Stacks & Queues
-
Trees
-
Graph
-
Greedy
-
Tries
-
Arrays
-
Binary Search Trees
-
Heap
-
Bit Manipulation
-

Maximum Length of Chain

Contributed by
Nishant Chitkara
Medium
Avg time to solve 15 mins
Success Rate 85 %
Share
2 upvotes

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.

Detailed explanation ( Input/output format, Notes, Constraints, Images )
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