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.
1function findLongestChain(pairs) {
2 pairs.sort((a, b) => a[1] - b[1]);
3 let currentEnd = Number.MIN_SAFE_INTEGER, count = 0;
4 for (let pair of pairs) {
5 if (pair[0] > currentEnd) {
6 currentEnd = pair[1];
7 count++;
8 }
9 }
10 return count;
11}
12
13console.log(findLongestChain([[1, 2], [2, 3], [3, 4]]));The JavaScript solution sorts the pairs array based on the second element, then uses a greedy algorithm to find the longest chain by tracking the current end.
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
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.
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.