646. 最长数对链

1. 先从题中找关键点
   1. 数对（a，b）中，b > a
   2. 数对链(a, b) (c, d)中，c > b
   3. 答案是找最长的数对链的长度
2. 可以先尝试将所有数对排序，看是否能找到最长的数对链。
   1. 可以分类讨论，将数对按第一个数排序后，在数对(a, b) (c, d)中
      1. 若c > b，那正好形成数对链
      2. 若d < b，在最长数对链中(c, d)可以取代(a, b)
   2. 因此用stack或list结构存储最长数对链，遍历排序后的数对
   3. 先看是否c > b，大于就放入数对链中；
   4. 若不大于，则看是否可以取代，也就是 d < b
   5. 若可以取代则取代，不行则继续遍历
   6. 如此一次遍历就可以找到最长的数对链
   7. 时间复杂度：排序用了O(nlogn)，后面再遍历一次O(n)，所以是O(nlogn)
3. 也可以用DP来做
   1. 将数对按第一个数排序后
   2. 用int[] dp记录以每个数对结尾的数对链的长度，dp[i]的长度就是前一个满足条件的dp[j]+1
   3. 时间复杂度：O(n^2)

approach 1，排序+贪心

class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> {
            if (a[0] == b[0]) {
                return a[1] - b[1];
            } else {
                return a[0] - b[0];
            }
        });

        Stack<int[]> stack = new Stack<>();
        for (int[] p : pairs) {
            if (stack.empty()) {
                stack.push(p);
                continue;
            }

            int[] peek = stack.peek();
            if (p[0] > peek[1]) {
                stack.push(p);
            } else if (peek[1] > p[1]) {
                stack.pop();
                stack.push(p);
            }
        }

        return stack.size();
    }
}

approach 2，排序+DP

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