[Java] Very Simple without DP

  • 7

    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
                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.