Leetcode 646. Maximum Length of Pair Chain

[Woodyiiiiiii]

这道题一看就是LIS类型的题目。

而且，更重要的是，题目要求的是结果的个数，而不是所有的结果，这样就能用DP了。如果是后者，则需要用Backtrack回溯法了。

class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            }
            return o1[0] - o2[0];
        });
        int[][] dp = new int[pairs.length + 1][2];
        dp[0][0] = Integer.MIN_VALUE;
        dp[0][1] = Integer.MIN_VALUE;
        int len = 0;
        for (int[] pair : pairs) {
            if (dp[len][1] < pair[0]) {
                dp[++len][0] = pair[0];
                dp[len][1] = pair[1];
            }
            for (int i = len; i > 0; --i) {
                if (dp[i - 1][1] < pair[0] && dp[i][1] > pair[1]) {
                    dp[i][0] = pair[0];
                    dp[i][1] = pair[1];
                }
            }
        }
        return len;
    }
}

其实更简化点的DP做法是，直接dp[i] = Math.max(dp[i], dp[j] + 1)。因为LIS的做法是为了能够达到O(nlgn)的时间复杂度，但我还没想到...

另一个做法是贪心。

class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (o1, o2) -> {
            return o1[1] - o2[1];
        });
        int len = 1;
        int[] lastPair = pairs[0];
        for (int i = 1; i < pairs.length; ++i) {
            if (pairs[i][0] > lastPair[1]) {
                ++len;
                lastPair = pairs[i];
            }
        }
        return len;
    }
}

---

• 646. Maximum Length of Pair Chain
• https://leetcode.com/problems/maximum-length-of-pair-chain/solutions/3043999/java-greedy-commented-explanation/