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.
1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
5 return ((int *)a)[1] - ((int *)b)[1];
6}
7
8int findLongestChain(int pairs[][2], int pairsSize) {
9 qsort(pairs, pairsSize, sizeof(pairs[0]), compare);
10 int count = 0, currentEnd = INT_MIN;
11 for (int i = 0; i < pairsSize; i++) {
12 if (pairs[i][0] > currentEnd) {
13 count++;
14 currentEnd = pairs[i][1];
15 }
16 }
17 return count;
18}
19
20int main() {
21 int pairs[][2] = {{1,2},{2,3},{3,4}};
22 printf("%d\n", findLongestChain(pairs, 3));
23 return 0;
24}This C solution sorts the pairs by their second element using qsort. It then iterates through the sorted pairs, maintaining the current end of the chain. If the current start of the pair is greater than the current end, it extends the chain.
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.
1function
In JavaScript, dp is an array tracking the longest chain ending with each pair. It utilizes nested loops to update dp and track the overall maximum length as it processes.