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.
1import java.util.*;
2
3public class PairChain {
4 public static int findLongestChain(int[][] pairs) {
5 Arrays.sort(pairs, Comparator.comparingInt(a -> a[1]));
6 int currentEnd = Integer.MIN_VALUE, count = 0;
7 for (int[] pair : pairs) {
8 if (pair[0] > currentEnd) {
9 currentEnd = pair[1];
10 count++;
11 }
12 }
13 return count;
14 }
15
16 public static void main(String[] args) {
17 int[][] pairs = {{1, 2}, {2, 3}, {3, 4}};
18 System.out.println(findLongestChain(pairs));
19 }
20}In Java, this solution sorts the array of pairs using a lambda expression for comparing the second elements. It uses a greedy approach to determine the maximum length of a chain that can be formed.
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.
1using System;
using System.Collections.Generic;
public class PairChain {
public static int FindLongestChain(int[][] pairs) {
Array.Sort(pairs, (a, b) => a[0].CompareTo(b[0]));
int[] dp = new int[pairs.Length];
Array.Fill(dp, 1);
int maxLen = 1;
for (int i = 1; i < pairs.Length; i++) {
for (int j = 0; j < i; j++) {
if (pairs[j][1] < pairs[i][0]) {
dp[i] = Math.Max(dp[i], dp[j] + 1);
}
}
maxLen = Math.Max(maxLen, dp[i]);
}
return maxLen;
}
public static void Main() {
int[][] pairs = new int[][] { new int[] {1, 2}, new int[] {2, 3}, new int[] {3, 4} };
Console.WriteLine(FindLongestChain(pairs));
}
}In C#, the array dp stores the length of the longest chain ending with each pair. By comparing with all earlier pairs, it updates dp values to reflect the longest possible chains.