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.
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
The Python implementation constructs the dp array initialized to 1. It sorts the pairs by their first element and fills in dp based on possible chains, ultimately determining the maximum length.