646. Maximum Length of Pair Chain

class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> Integer.compare(a[0], b[0]));
        // index means the length of the chain and the element means the last pair's 1st
        // element
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < pairs.length; i++) {
            int targetChainIdx = binarySearch(list, pairs[i][0]);
            if (targetChainIdx + 1 == list.size()) {
                list.add(pairs[i][1]);
            } else {
                list.set(targetChainIdx + 1, Math.min(list.get(targetChainIdx + 1), pairs[i][1]));
            }
        }
        return list.size();
    }

    private int binarySearch(List<Integer> list, int target) {
        int left = 0, right = list.size() - 1, ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid) < target) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
}

第300题.
sort一下pairs. 让每一个pair都做chain的最后一个, 看每个pair做chain最后一个的时候, 最长的能有多长, 然后再得到全局最大即可. 这和有道题求最长递增数列有点儿像, 也是用list来记录前面的元素做数列尾部的时候, 最长的长度是多少, 同时记录达到某个长度的末尾最小可以是多少. 这样方便后面的数字来和往后加.

问题就是为什么sort? 因为如果一个pair后面出现一个很大的pair, 这样二者可以结合成一个chain, 但如果再之后出现了一个很小的pair, 并且可以夹在它们之间, 我们就catch不到这种情况, 于是我们sort一下, 让pair[0]小的往前走, 这样如果能配上对的, 那就会捕捉到, 否则就是配不上对的.

时间复杂度: O(nlogn)
空间复杂度: O(n) 可能list一直在增长