Maximum Length of Pair Chain

https://leetcode.com/problems/maximum-length-of-pair-chain/description/

You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.

Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion.

Given a set of pairs, find the length longest chain which can be formed. You needn't use up all the given pairs. You can select pairs in any order.

Example 1:

Input: [[1,2], [2,3], [3,4]]

Output: 2

Explanation: The longest chain is [1,2] -> [3,4]

Thoughts

数组最长想到DP. 我们可以写一组出来，比如[3, 4], [1, 2], [5, 6]能构成长度为3的chain。 在构成[1, 2] [3, 4] [5, 6]时可以重复利用[1, 2], [3, 4]的结果。但想利用必须要排好序。 因此我们可以设f[i]为以i为结尾时最长链长度，再用一个循环找0~i-1中能和i连起来的且f值最大的。

Code

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

        }
        return max;
    }

}

Analysis

Errors: 1. 题目没看清。要求是小于即可，不要求是连着。 时间复杂度O(n^2).

Ver.2

如果例子写长点会发现f的值不会减少。这是因为f[i]如果比f[i-1]小，则表明0~i-2中比能与i相连的比与能与i-1相连的少。然而这是不可能的，因为排好序的情况下前面的pair的第二个数比i-1第一个数小肯定也比第i个数的第一个数小。因此我们可以把max变量省掉，并且把内循环换成二分法，时间复杂度就成了O(nlgn).