package leetcode;

import java.util.Arrays;

/**
 * https://leetcode.com/problems/maximum-length-of-pair-chain/
 */
public class Problem646 {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> {
            int cmp = Integer.compare(a[0], b[0]);
            if (cmp == 0) {
                return Integer.compare(a[1], b[1]);
            }
            return cmp;
        });
        return findLongestChain(pairs, 0);
    }

    private static int findLongestChain(int[][] pairs, int idx) {
        if (idx == pairs.length) {
            return 0;
        }
        int max = 0;
        int[] current = pairs[idx];
        for (int i = idx + 1; i < pairs.length; i++) {
            int[] next = pairs[i];
            int val = 1;
            if (current[1] < next[0]) {
                val++;
            }
            max = Math.max(max, findLongestChain(pairs, i + 1) + val);
        }
        return max;
    }

    public static void main(String[] args) {
        Problem646 prob = new Problem646();
//        System.out.println(prob.findLongestChain(new int[][]{{1, 2}, {2, 3}, {3, 4}})); // 2
//        System.out.println(prob.findLongestChain(new int[][]{{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}})); // 3
//        System.out.println(prob.findLongestChain(new int[][]{{1, 2}, {2, 3}, {3, 4}, {4, 5}})); // 2
//        System.out.println(prob.findLongestChain(new int[][]{{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {7, 8}})); // 4
        System.out.println(prob.findLongestChain(new int[][]{{-1, 0}, {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {7, 8}})); // 5
    }
}

@@ -416,41 +416,221 @@
     
-return findLongestChain(pairs, 0)
+Integer%5B%5D memo = new Integer%5Bpairs.length%5D;%0A        int max = 0;%0A        for (int i = 0; i %3C pairs.length; i++) %7B%0A            max = Math.max(max, findLongestChain(pairs, i, memo) + 1);%0A        %7D%0A        return max
 ;%0A  
@@ -696,16 +696,32 @@
  int idx
+, Integer%5B%5D memo
 ) %7B%0A    
@@ -775,32 +775,105 @@
 rn 0;%0A        %7D%0A
+        if (memo%5Bidx%5D != null) %7B%0A            return memo%5Bidx%5D;%0A        %7D%0A
         int max 
@@ -1007,33 +1007,8 @@
 i%5D;%0A
-            int val = 1;%0A
     
@@ -1051,41 +1051,8 @@
     
-            val++;%0A            %7D%0A
     
@@ -1108,19 +1108,19 @@
 s, i
- + 1
+, memo
 ) + 
-val
+1
 );%0A 
@@ -1129,680 +1129,69 @@
     
- %7D%0A
      
-   return max;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem646 prob = new Problem646();%0A//        System.out.println(prob.findLongestChain(new int%5B%5D%5B%5D%7B%7B1, 2%7D, %7B2, 3%7D, %7B3, 4%7D%7D)); // 2%0A//        System.out.println(prob.findLongestChain(new int%5B%5D%5B%5D%7B%7B1, 2%7D, %7B2, 3%7D, %7B3, 4%7D, %7B4, 5%7D, %7B5, 6%7D%7D)); // 3%0A//        System.out.println(prob.findLongestChain(new int%5B%5D%5B%5D%7B%7B1, 2%7D, %7B2, 3%7D, %7B3, 4%7D, %7B4, 5%7D%7D)); // 2%0A//        System.out.println(prob.findLongestChain(new int%5B%5D%5B%5D%7B%7B1, 2%7D, %7B2, 3%7D, %7B3, 4%7D, %7B4, 5%7D, %7B5, 6%7D, %7B7, 8%7D%7D)); // 4%0A        System.out.println(prob.findLongestChain(new int%5B%5D%5B%5D%7B%7B-1, 0%7D, %7B1, 2%7D, %7B2, 3%7D, %7B3, 4%7D, %7B4, 5%7D, %7B5, 6%7D, %7B7, 8%7D%7D)); // 5
+%7D%0A        %7D%0A        memo%5Bidx%5D = max;%0A        return max;
 %0A   

Solve problem 646