题目

题目来源：力扣（LeetCode）

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

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

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


示例：

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

思路分析

动态规划

子序列类型动态规划，即pairs[i]能否拼接在某个pairs[j]后，并取最长子序列
由于最后结果不限制初始位置，所以先用排序预处理下，使得原始序列竟可能递增排列

状态定义
dp[i]：以pairs[i]结尾的最长数对链长度

状态转移
遍历 j=1..i-1,如果pairs[j][1] < pairs[i][0],则dp[i]=dp[j]+1

代码实现

  1. /**
  2.  * @param {number[][]} pairs
  3.  * @return {number}
  4.  */
  5. var findLongestChain = function (pairs) {
  6.   if (!pairs || pairs.length === 0) return 0
  7.   if (pairs.length === 1) return 1
  8.   //排序，想到排序是因为一条链是整体升序的
  9.   pairs.sort((a, b) => a[0] - b[0])
  10.   //存储以i结尾的最长链的长度
  11.   let dp = new Array(pairs.length).fill(1)
  12.   let ans = 0
  13.   for (let i = 1; i < pairs.length; i++) {
  14.     //找到某个j，如果i能加入j，就得到一条比j更长的链，然后找到能形成的最长的
  15.     for (let j = i - 1; j > -1; j--) {
  16.       if (pairs[j][1] < pairs[i][0]) {
  17.         dp[i] = Math.max(dp[i], dp[j] + 1)
  18.       }
  19.     }
  20.     ans = Math.max(dp[i], ans)
  21.   }
  22.   return ans
  23. };

贪心思想

  1. 希望找到尽可能长的数对链，贪心的思想，我们需要当前数对链的结尾值尽可能的小。
  2. 比如当前有[1,2]，后续可以提供选择的有[3,4],[3,8]，那么显然，我们优先选取[3,4]，才能让选出的数对尽可能的多。
  3. 首先，我们对pairs中的数组，按照第二个元素升序的顺序进行排序，如此，只需按顺序遍历，即可保证不会遗漏，且能得到我们想要的结果。
  4. 第一个必选，然后记录当前的尾部值，只要之后的数组起始值大于当前的尾部值，结果+1。同时更新尾部值。
    1. var findLongestChain = function (pairs) {
    2. //先给pairs以第二位的大小从小到大拍好序
    3. let orderedpairs = pairs.sort((a, b) => {
    4.  return a[1] - b[1]
    5. })
    6. //初始化count为1（把第一个节点算进去），之后只要候选的第一位大于start节点的第二位，说明可以接到后面
    7. let count = 1
    8. let start = orderedpairs[0]
    9. for (let i = 1; i < orderedpairs.length; i++) {
    10.  if (orderedpairs[i][0] > start[1]) {
    11.    //可以接的话，count+1，start节点重置为新的节点
    12.    count++
    13.    start = orderedpairs[i]
    14.  }
    15. }
    16. return count
    17. };