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 <= 1000The goal in #646 Maximum Length of Pair Chain is to find the longest sequence of pairs where the second value of one pair is smaller than the first value of the next. This problem resembles interval scheduling and can be approached using greedy or dynamic programming techniques.
A common strategy is to first sort the pairs. In the greedy approach, pairs are sorted by their ending value. Then, we iterate through them and select a pair only if its start value is greater than the end of the last chosen pair. This works because choosing the pair with the smallest ending value leaves more room for future pairs.
Alternatively, a dynamic programming method treats the problem similarly to the Longest Increasing Subsequence (LIS). After sorting the pairs, we compute the best chain ending at each pair by checking all previous compatible pairs.
The greedy solution is typically preferred due to its efficiency, achieving O(n log n) time for sorting and linear traversal.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy with Sorting | O(n log n) | O(1) |
| Dynamic Programming (LIS-style) | O(n^2) | O(n) |
GeeksforGeeks
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.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as it sorts in-place.
1import java.util.*;
2
3public class PairChain {
4 public static int findLongestChain(int[][] pairs)
In Java, this solution sorts the array of pairs using a lambda expression for comparing the second elements. It uses a greedy approach to determine the maximum length of a chain that can be formed.
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.
Time Complexity: O(n^2)
Space Complexity: O(n) due to the DP array.
1#include <vector>
#include <algorithm>
#include <iostream>
int findLongestChain(std::vector<std::vector<int>>& pairs) {
std::sort(pairs.begin(), pairs.end());
std::vector<int> dp(pairs.size(), 1);
int maxLen = 1;
for (int i = 1; i < pairs.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (pairs[j][1] < pairs[i][0]) {
dp[i] = std::max(dp[i], dp[j] + 1);
}
}
maxLen = std::max(maxLen, dp[i]);
}
return maxLen;
}
int main() {
std::vector<std::vector<int>> pairs = {{1, 2}, {2, 3}, {3, 4}};
std::cout << findLongestChain(pairs) << std::endl;
return 0;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of interval scheduling and chain problems like this appear in FAANG-style interviews. Interviewers often expect candidates to recognize the greedy strategy after sorting intervals by their end values.
The problem primarily uses arrays along with sorting. After sorting the pairs, simple variables or counters are enough for the greedy approach, while the dynamic programming method may use an additional DP array to track the best chain length ending at each pair.
The optimal approach is a greedy strategy where pairs are sorted by their ending value. By always selecting the pair with the smallest possible end that still forms a valid chain, we maximize the number of pairs that can follow. This approach runs in O(n log n) time due to sorting.
Yes, the dynamic programming approach is conceptually similar to the Longest Increasing Subsequence problem. Each pair can extend a previous chain if its start value is greater than the end value of the previous pair.
C++ implementation uses a DP array initialized to 1. The pairs are sorted by the first element, and a nested loop constructs the longest possible chains, updating the DP array accordingly.