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.
1using System;
2using System.Collections.Generic;
3
4public class PairChain {
5 public static int FindLongestChain(int[][] pairs) {
6 Array.Sort(pairs, (a, b) => a[1].CompareTo(b[1]));
7 int currentEnd = int.MinValue, count = 0;
8 foreach (var pair in pairs) {
9 if (pair[0] > currentEnd) {
10 currentEnd = pair[1];
11 count++;
12 }
13 }
14 return count;
15 }
16
17 public static void Main() {
18 int[][] pairs = new int[][] { new int[] {1, 2}, new int[] {2, 3}, new int[] {3, 4} };
19 Console.WriteLine(FindLongestChain(pairs));
20 }
21}This C# solution sorts the pairs by their second element using Array.Sort with a custom comparator. It then keeps track of the current end of the longest 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.
1#
The C implementation initializes a DP array with 1, as each pair can be a chain of length 1. It sorts the pairs by the first element, then uses nested loops to populate the DP table, calculating the maximum length for each position.