You are given an array of n pairs pairs where pairs[i] = [lefti, righti] and lefti < righti.
A pair p2 = [c, d] follows a pair p1 = [a, b] if b < c. A chain of pairs can be formed in this fashion.
Return the length longest chain which can be formed.
You do not need to use up all the given intervals. You can select pairs in any order.
Example 1:
Input: pairs = [[1,2],[2,3],[3,4]] Output: 2 Explanation: The longest chain is [1,2] -> [3,4].
Example 2:
Input: pairs = [[1,2],[7,8],[4,5]] Output: 3 Explanation: The longest chain is [1,2] -> [4,5] -> [7,8].
Constraints:
n == pairs.length1 <= n <= 1000-1000 <= lefti < righti <= 1000This approach involves sorting the pairs by their second element and then greedily selecting pairs that can extend the chain. The intuition here is that by picking the pairs with the smallest possible ending, we maintain maximum flexibility for extending the chain.
This C solution sorts the pairs by their second element using qsort. It then iterates through the sorted pairs, maintaining the current end of the chain. If the current start of the pair is greater than the current end, it extends the chain.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as it sorts in-place.
This approach uses dynamic programming to determine the longest chain. We first sort the pairs based on the first element. Then, we define a DP array where dp[i] represents the length of the longest chain ending with the i-th pair.
The C implementation initializes a DP array with 1, as each pair can be a chain of length 1. It sorts the pairs by the first element, then uses nested loops to populate the DP table, calculating the maximum length for each position.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2)
Space Complexity: O(n) due to the DP array.
| Approach | Complexity |
|---|---|
| Greedy Approach with Sorting | Time Complexity: O(n log n) due to sorting. |
| Dynamic Programming Approach | Time Complexity: O(n^2) |
Maximum Length Chain of Pairs | Dynamic Programming (Set 20) | GeeksforGeeks • GeeksforGeeks • 24,951 views views
Watch 9 more video solutions →Practice Maximum Length of Pair Chain with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor