Concise Java DP solution.


  • 0
    G

    Simliar as LIS. dp[i] = max(dp[i], dp[j]+1).

    public int findLongestChain(int[][] pairs) {
          if (pairs.length == 0)  return 0;
          int len = pairs.length;
          Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
          int[] dp = new int[len];
          Arrays.fill(dp, 1);
          int max = 1;
          for (int i = 1; i < len; i++) {
            int[] cur = pairs[i];
            for (int j = 0; j < i; j++) {
              int[] pre = pairs[j];
              if (cur[0] > pre[1]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
                max = Math.max(dp[i], max);
              }
            }
          }
          return max;
      }
    

Log in to reply
 

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