Java O(nlog(n)) DP


  • 0
    M
    public class Solution {
        public int findLongestChain(int[][] pairs) {
            Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));
            int[] dp = new int[pairs.length];
            for (int i = 0; i < pairs.length; i++) {
                int j = i - 1;
                while (j >= 0) {
                    if (pairs[j][1] < pairs[i][0])
                        break;
                    j--;
                }
                if (j < 0)
                    dp[i] = 1;
                else
                    dp[i] = dp[j] + 1;
            }
            return dp[pairs.length - 1];
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.