[Java] Very Simple without DP


  • 3
    L

    This question actually can be transferred into a similar problem,
    "Maximum Length of Increasing Subsequence of Integer Array -- The subsequence can be formed in any order".
    The slight difference is that you need detect the overlap between current pair and previous pair.
    I just solved this problem by the rule I observed instead of by the thoughts of DP.

    Time: O(N logN)
    Space: O(1)

    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (p1, p2)->p1[0]-p2[0]);
        int len = 0;
        int pre = Integer.MIN_VALUE;
        for(int[] pair : pairs){
            if(pair[0] > pre){  // not overlap
                len++;
                pre = pair[1];
             }else if(pair[1] < pre){ // overlap but with smaller second element
                pre = pair[1];
            }
        }
        return len;
    }
    

Log in to reply
 

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