Sponsored
Sponsored
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.
1def findLongestChain(pairs):
2 pairs.sort(key=lambda x: x[1])
3 current_end = float('-inf')
4 count = 0
5 for pair in pairs:
6 if pair[0] > current_end:
7 current_end = pair[1]
8 count += 1
9 return count
10
11pairs = [[1, 2], [2, 3], [3, 4]]
12print(findLongestChain(pairs))The Python solution uses sort with a lambda function to arrange the pairs based on the second element. It then applies the greedy logic to find the longest chain of pairs.
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;
}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.