2 Java methods, O(nlogn) and dp O(n^2)


  • 0
    M
    // ---------------- method 1: DP, O(N^2) ----------------
        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);
            int maxLen = 1;
            for(int i=1; i<pairs.length; i++){
                for(int j=0; j<i; j++){
                    if(pairs[i][0]>pairs[j][1] && dp[i]<dp[j]+1){
                        dp[i] = dp[j] + 1;
                        maxLen = Math.max(maxLen, dp[i]);
                    }
                }
            }
            return maxLen;
        }
    
    // ---------------- method 2: O(N) ----------------
        public int findLongestChain(int[][] pairs) {
            if(pairs==null || pairs.length==0) return 0;
            Arrays.sort(pairs, (a,b)->(a[1]-b[1]));
            int count = 1, max = pairs[0][1];
            for(int i=1; i<pairs.length; i++){
                if(pairs[i][0] > max){
                    max = pairs[i][1];
                    count++;
                }
            }
            return count;
        }
    

  • 0

    ese es greedy


Log in to reply
 

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