0646. 最长数对链【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 贪心

1. 📝 题目描述

• leetcode

给你一个由 n 个数对组成的数对数组 pairs，其中 pairs[i] = [lefti, righti] 且 lefti < righti。

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

找出并返回能够形成的 最长数对链的长度。

你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

---

示例 1：

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

示例 2：

输入：pairs = [[1,2],[7,8],[4,5]]
输出：3
解释：最长的数对链是 [1,2] -> [4,5] -> [7,8]。

---

提示：

• n == pairs.length
• 1 <= n <= 1000
• -1000 <= lefti < righti <= 1000

2. 🎯 s.1 - 贪心

c

int cmp(const void* a, const void* b) {
    return (*(int**)a)[1] - (*(int**)b)[1];
}

int findLongestChain(int** pairs, int pairsSize, int* pairsColSize) {
    qsort(pairs, pairsSize, sizeof(int*), cmp);
    int count = 1, end = pairs[0][1];
    for (int i = 1; i < pairsSize; i++) {
        if (pairs[i][0] > end) {
            count++;
            end = pairs[i][1];
        }
    }
    return count;
}

js

/**
 * @param {number[][]} pairs
 * @return {number}
 */
var findLongestChain = function (pairs) {
  pairs.sort((a, b) => a[1] - b[1])
  let count = 1,
    end = pairs[0][1]
  for (let i = 1; i < pairs.length; i++) {
    if (pairs[i][0] > end) {
      count++
      end = pairs[i][1]
    }
  }
  return count
}

py

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        pairs.sort(key=lambda x: x[1])
        count, end = 1, pairs[0][1]
        for i in range(1, len(pairs)):
            if pairs[i][0] > end:
                count += 1
                end = pairs[i][1]
        return count

• 时间复杂度：$O(n\log n)$，其中 n 是数对数量
• 空间复杂度：$O(\log n)$，排序的栈空间

算法思路：

• 按右端点升序排序，等同于活动选择问题
• 贪心选择右端点最小的数对，保证剩余空间最大