题目名称

给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。

现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。

给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

示例

输入：[[1,2], [2,3], [3,4]]
输出：2
解释：最长的数对链是 [1,2] -> [3,4]

题解

对数组根据数组元素的第二个数的大小进行排序，保证(a,b)和(c,d)中， b 永远是小于d的。

然后遍历数组，这里使用的双重循环遍历，第一个循环主要用来确定数队链的首个元素，第二个循环遍历剩余元素中满足(a,b)和(c,d)中 b < c

最后，将每个循环所得到的的数队链的最大长度进行比较，取最大值

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number[][]} pairs
 * @return {number}
 */
var findLongestChain = function(pairs) {
    pairs = pairs.sort((a, b) => a[1] - b[1])
    let max = 1
    for(let i = 0; i < pairs.length - 1; i++) {
        let p = pairs[i][1]
        let length = 1
        let j = i + 1
        while(j < pairs.length) {
            if(p < pairs[j][0]) {
                length++
                p = pairs[j][1]
            }
            j++
        }
        max = Math.max(max, length)
    }
    return max
};