646. Maximum Length of Pair Chain
Problem Description
You are provided with an array of n pairs, with each pair formatted as [left_i, right_i], and it's guaranteed that left_i < right_i for each pair. The concept of one pair "following" another is introduced as such: a pair p2 = [c, d] is said to follow another pair p1 = [a, b] if b < c. Chains can be formed by linking pairs that follow one another. The aim is to find the length of the longest possible chain of pairs that can be built from the given array. It's important to note that there is no requirement to use all the pairs provided; you are free to choose any sequence of pairs that forms the longest possible chain.
Intuition
The intuition behind the problem solution is to apply a greedy algorithm. The key idea of the greedy approach is to always choose the next pair in the chain with the smallest second element that is not yet connected to the chain. This is because selecting the pair with the smallest right_i minimizes the chance of precluding the selection of future pairs while maximizing the potential chain length.
How do we implement this strategy? First, we sort the pairs in ascending order based on their right_i components. Sorting by the second element ensures that as we iterate through the pairs, we always have the pair with the smallest possible right_i that could extend our current chain.
Once the pairs are sorted, we loop over them and keep track of the current end of the chain we have built (initially, we use negative infinity to ensure we can start our chain with the first pair). For each pair, we compare the current end of the chain (cur) with the start of the next pair (a). If cur < a, then the current pair can be appended to the chain, extending it by one. Then we set cur to the end of the current pair (b) and increase our chain length count (ans).
This approach guarantees we'll end up with the longest chain by always choosing pairs that extend the chain while blocking the fewest possible pairs that come after.
Learn more about Greedy, Dynamic Programming and Sorting patterns.
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
Solution Approach
The implementation of the provided solution involves the use of the greedy algorithm and is grounded in Python's list sorting capabilities. Here is a step-by-step explanation of the solution approach:
-
We start by sorting the
pairslist. The sorting is done based on the second element of each pair (right_i) using a lambda function as the key:sorted(pairs, key=lambda x: x[1]). This arranges the pairs in ascending order of theirright_ivalues, allowing us to consider the pairs that preclude the fewest future pairs first when forming the chain. -
An
ansvariable is initialized to0, which will eventually represent the length of the longest chain of pairs. Thecurvariable is set to negative infinity (-inf) to ensure that the first pair in the sorted list can be taken as the starting pair of the chain. -
A for loop is used to iterate over each pair in the sorted pairs list. At each step, the loop checks whether the current pair
[a, b]can follow the last pair added to the chain. Specifically, it checks ifcur < a:- If
cur < a, this means that the current chain (currepresenting the end of the last pair in the chain) does not overlap with the starting point of the current pair (a), hence the current pair can be appended to the chain. - The
curvariable is updated to the value ofbof the current pair, which becomes the new end of the chain. - The
ans(answer) variable is incremented by1since we just added a pair to our chain.
- If
-
After the loop finishes, the variable
ansholds the length of the longest chain that can be formed and is returned as the final result.
By utilizing this approach, each pair is added to the chain optimally, ensuring that we can move to the next possible pair without excluding too many other pairs. This implementation is efficient and demonstrates the power of the greedy algorithm in solving such problems.
Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Example Walkthrough
Consider the list of pairs: pairs = [[1, 2], [2, 3], [3, 4]].
-
We first sort the
pairsby their second element, resulting in no change in this case since the array is already sorted byright_i:[[1, 2], [2, 3], [3, 4]]. -
Initialize
ansto0. This variable keeps track of the length of the longest chain. -
Initialize
curto negative infinity (-inf) to ensure that we can compare it with the first elementaof the first pair. -
Now we start looping through each sorted pair:
- First pair is
[1, 2]. We comparecur (-inf) < 1. Since this is true, we can start a chain with this pair. Therefore, we updatecurto2(the second element of the pair) and incrementansto1. - Next pair is
[2, 3]. We comparecur (2) < 2. This is false, so we cannot include this pair in our chain â it conflicts with the previous pair[1, 2]. - The last pair is
[3, 4]. We comparecur (2) < 3. This is true, so we can append this pair to our chain. We updatecurto4and incrementansto2.
- First pair is
-
By the end of the loop,
ansis2, representing the length of the longest chain, which includes the pairs[1, 2]and[3, 4].
This example demonstrates the application of the greedy algorithm where we prioritize adding pairs to our chain based on the smallest right_i that doesn't overlap with the current chain. The longest chain possible in this case is of length 2, which is our final result.
Solution Implementation
1from typing import List
2
3class Solution:
4 def findLongestChain(self, pairs: List[List[int]]) -> int:
5 # Initialize the variable to store the length of the longest chain and
6 # the current end value of the last pair in the chain
7 longest_chain_length, current_end = 0, float('-inf')
8
9 # Sort the pairs based on their second element since we want to ensure
10 # we pick the next pair with the smallest possible end value.
11 for start, end in sorted(pairs, key=lambda x: x[1]):
12 # If the current start is greater than the last stored end,
13 # it means we can append the current pair to the chain.
14 if current_end < start:
15 current_end = end # Update the end to the current pair's end
16 longest_chain_length += 1 # Increase the length of the chain
17
18 # Return the length of the longest chain found
19 return longest_chain_length
201class Solution {
2 public int findLongestChain(int[][] pairs) {
3 // Sort the pairs array by the second element of each pair (i.e., end time of the interval)
4 Arrays.sort(pairs, Comparator.comparingInt(pair -> pair[1]));
5
6 // Initialize the count of the longest chain as 0
7 int longestChainLength = 0;
8
9 // Initialize 'currentEnd' to the minimum integer value
10 int currentEnd = Integer.MIN_VALUE;
11
12 // Iterate through the sorted pairs
13 for (int[] pair : pairs) {
14 // If the current pair's start time is greater than 'currentEnd'
15 if (currentEnd < pair[0]) {
16 // Update 'currentEnd' to the end time of the current pair
17 currentEnd = pair[1];
18
19 // Increment the count of the chain as we've found a non-overlapping pair
20 ++longestChainLength;
21 }
22 }
23
24 // Return the length of the longest chain found
25 return longestChainLength;
26 }
27}
281#include <vector> // Include vector header for using vectors
2#include <climits> // Include limits header for using INT_MIN
3
4using namespace std; // Use standard namespace
5
6class Solution {
7public:
8 int findLongestChain(vector<vector<int>>& pairs) {
9 // Sort the vector of pairs by the second element of each pair
10 sort(pairs.begin(), pairs.end(), [](const vector<int>& a, const vector<int>& b) {
11 return a[1] < b[1];
12 });
13
14 int chainLength = 0; // Initialize the length of the longest chain to 0
15 int currentEnd = INT_MIN; // Initialize the end of current pair to the minimum integer value
16
17 // Iterate over all the pairs
18 for (const auto& pair : pairs) {
19 // If the current pair can be chained to the previous one
20 if (currentEnd < pair[0]) {
21 currentEnd = pair[1]; // Update the end of current pair
22 ++chainLength; // Increment the length of the chain
23 }
24 }
25
26 // Return the length of the longest chain found
27 return chainLength;
28 }
29};
301function findLongestChain(pairs: number[][]): number {
2 // Sort the array of pairs based on the second element of each pair
3 pairs.sort((firstPair, secondPair) => firstPair[1] - secondPair[1]);
4
5 // Initialize the count of the longest chain
6 let longestChainCount = 0;
7
8 // Initialize the previous end element of the last pair in the chain to negative infinity
9 let previousEnd = -Infinity;
10
11 // Iterate through each pair in the sorted array
12 for (const [start, end] of pairs) {
13 // If the current pair's start is greater than the end of the last pair added to the chain
14 if (previousEnd < start) {
15 // Update the previous end to the current pair's end
16 previousEnd = end;
17
18 // Increment the count of the longest chain
19 longestChainCount++;
20 }
21 }
22
23 // Return the count of the longest possible chain
24 return longestChainCount;
25}
26Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Time and Space Complexity
The time complexity of the given code is primarily dictated by the sorting operation. Sorting an array of pairs with a total of n pairs has a time complexity of O(n log n). The for-loop that follows has a time complexity of O(n), as it iterates through the list of pairs only once. Therefore, the overall time complexity of the algorithm is O(n log n) due to the sorting step, since O(n log n) + O(n) simplifies to O(n log n).
Additionally, the space complexity of the code is O(1) or constant space complexity, since no additional space that scales with the input size is used, and the sorting is done in-place, assuming the sorting algorithm used is space-optimized, like Timsort, which is the default sorting algorithm in Python. The only extra variables used are for the current end of the chain (cur) and the answer counter (ans), which both require a constant amount of space.
Learn more about how to find time and space complexity quickly using problem constraints.
Depth first search can be used to find whether two components in a graph are connected.
Recommended Readings
Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.