[646. Maximum Length of Pair Chain] #leetcode

646_0829.java

class Solution {
  // O(n^2) O(n)
    public int findLongestChain(int[][] pairs) {
        if (pairs == null || pairs.length == 0) return 0;
        
        Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));
        int[] dp = new int[pairs.length];
        Arrays.fill(dp, 1);
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] = Math.max(dp[i], pairs[i][0] > pairs[j][1]? dp[j] + 1 : dp[j]);
            }
        }
        return dp[pairs.length-1];
    }
}

class Solution1 {
  // O(nlogn) O(1)
    public int findLongestChain(int[][] pairs) {
        if (pairs == null || pairs.length == 0) return 0;
        
        Arrays.sort(pairs, (a, b) -> (a[1] - b[1]));
        
        int right = Integer.MIN_VALUE, n = 0;
        for (int[] pair : pairs) {
            if ( right < pair[0] ) {
                right = pair[1];
                n += 1;
            }
        }
        return n;
    }
}