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 <= 1000Problem Overview: You are given an array of pairs where each pair [a, b] represents an interval. A pair [c, d] can follow [a, b] only if b < c. The goal is to build the longest possible chain of such pairs.
Approach 1: Dynamic Programming (O(n²) time, O(n) space)
This approach models the problem similarly to the Longest Increasing Subsequence. First sort the pairs by their starting value. Then iterate through the array and compute dp[i], the maximum chain length ending at pair i. For each pair i, check all previous pairs j and extend the chain when pairs[j][1] < pairs[i][0]. The transition becomes dp[i] = max(dp[i], dp[j] + 1). This guarantees the correct answer but requires a nested loop, giving O(n²) time and O(n) extra space. It’s a good baseline when learning dynamic programming patterns.
Approach 2: Greedy with Sorting (O(n log n) time, O(1) space)
The optimal insight is that the problem behaves like activity selection. Instead of maximizing chain length with DP, sort the pairs by their ending value and always pick the pair with the earliest finishing time that can extend the chain. After sorting, iterate once through the array while tracking the end of the last chosen pair. If the current pair's start is greater than the stored end, add it to the chain and update the end pointer. Sorting costs O(n log n) and the single pass costs O(n), with constant extra space.
The greedy rule works because choosing the smallest end leaves the most room for future pairs. This mirrors classic interval scheduling problems and commonly appears in greedy interview questions involving sorting and interval selection.
Recommended for interviews: The greedy sorting approach is what interviewers usually expect. The DP solution shows you understand the LIS-style formulation, but the greedy insight demonstrates stronger algorithmic reasoning and reduces complexity from O(n²) to O(n log n).
This 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.
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.
Time Complexity: O(n^2)
Space Complexity: O(n) due to the DP array.
We sort all pairs in ascending order by the second number, and use a variable pre to maintain the maximum value of the second number of the selected pairs.
We traverse the sorted pairs. If the first number of the current pair is greater than pre, we can greedily select the current pair, increment the answer by one, and update pre to the second number of the current pair.
After the traversal, we return the answer.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the number of pairs.
| Approach | Complexity |
|---|---|
| Greedy Approach with Sorting | Time Complexity: O(n log n) due to sorting. |
| Dynamic Programming Approach | Time Complexity: O(n^2) |
| Sorting + Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (LIS-style) | O(n²) | O(n) | When learning DP transitions or explaining the problem step‑by‑step in interviews |
| Greedy with Sorting | O(n log n) | O(1) | Optimal solution; best for large inputs and commonly expected in interviews |
Maximum Length of Pair Chain | Same as LIS | FULL INTUITION | DP Concepts & Qns - 13 | Leetcode-646 • codestorywithMIK • 21,320 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