# 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).