646. Maximum Length of Pair Chain

Link

Solution

• User dp to solve the LIS problem ( the check condition change to c > b)

• Since the pairs can be selected in any order. Traverse the orginal pairs can have missing cases. ex: [[3,4], [1, 2],] The anwser shall be 2 ([1,2] -> [3,4]), but if we travese original pairs array, we will get only 1.

  • Sort the pairs first

  • use [[1,2],[3,4]] to do the LIS

  Sort Pairs

T: O(N^2 + NlogN)

 public int findLongestChain(int[][] pairs) {
        if(pairs.length == 0) return 0;
        //Sort first, then everything is the same
        Arrays.sort(pairs, (a, b) -> (a[0] - b[0]));
        int max = 1;
        int[] dp = new int[pairs.length];
        Arrays.fill(dp, 1);
        for(int i = 0; i < pairs.length; i++){
            for(int j = 0; j < i; j++){
                if(pairs[i][0] > pairs[j][1]){
                    if(dp[i] < dp[j] + 1){
                        dp[i] = dp[j] + 1;
                        //count[i] = count[j]
                    }
                    else if (dp[i] == dp[j] + 1){
                        //count[i] += count[j]
                    }
                }
            }
            if(max < dp[i]){
                max = dp[i];
                //ret = count[i];
            }
            if( max == dp[i]){
                //ret += count[i];
            }
        }
        return max;
    }