Untitled

import java.util.Arrays;

public class LongestChain {
    public int findLongestChain(int[][] pairs) {
        // Step 1: Sort pairs by the first element
        Arrays.sort(pairs, (a, b) -> Integer.compare(a[0], b[0]));

        int n = pairs.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1); // Base case: each pair alone forms a chain of length 1

        int maxLength = 1;

        // Step 2: Find the longest chain
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (pairs[j][1] < pairs[i][0]) { // If pair j can chain with pair i
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLength = Math.max(maxLength, dp[i]); // Update global maximum
        }

        return maxLength;
    }

    public static void main(String[] args) {
        LongestChain solution = new LongestChain();
        int[][] pairs1 = {{1, 2}, {2, 3}, {3, 4}};
        int[][] pairs2 = {{1, 2}, {7, 8}, {4, 5}};
        
        System.out.println(solution.findLongestChain(pairs1)); // Output: 2
        System.out.println(solution.findLongestChain(pairs2)); // Output: 3
    }
}