646. 最长数对链

🟠   🔖  贪心 数组 动态规划 排序  🔗 力扣 LeetCode

题目

You are given an array of n pairs pairs where pairs[i] = [lefti, righti] and lefti < righti.

A pair p2 = [c, d] follows a pair p1 = [a, b] if b < c. A chain of pairs can be formed in this fashion.

Return the length longest chain which can be formed.

You do not need to use up all the given intervals. You can select pairs in any order.

Example 1:

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

Output: 2

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

Example 2:

Input: pairs = [[1,2],[7,8],[4,5]]

Output: 3

Explanation: The longest chain is [1,2] -> [4,5] -> [7,8].

Constraints:

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

题目大意

给你一个由 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

解题思路

1. 排序 pairs

   • 先按照区间的 起始值 pairs[i][0] 进行升序排序，保证遍历时的顺序有序。

2. 定义 dp 数组

   • dp[i]：表示 以 pairs[i] 结尾的最长数对链的长度。
   • 初始化 dp[i] = 1，因为单独的 pairs[i] 本身就是一个长度为 1 的链。

3. 双层循环构建 dp

   • 遍历 pairs[i] 之前的 pairs[j]：
     • 如果 pairs[i][0] > pairs[j][1]，说明 pairs[i] 可以接在 pairs[j] 之后形成更长的数对链，更新 dp[i] = max(dp[i], dp[j] + 1)。

4. 求出最长数对链的长度

   • Math.max(...dp) 遍历 dp，得到最长的链长度。

复杂度分析

• 时间复杂度：O(n^2)，双层循环构建 dp。
• 空间复杂度：O(n)，用于存储 dp 数组。

代码

/**
 * @param {number[][]} pairs
 * @return {number}
 */
var findLongestChain = function (pairs) {
	pairs.sort((a, b) => a[0] - b[0]);
	const n = pairs.length;
	const dp = new Array(n).fill(1);
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < i; j++) {
			if (pairs[i][0] > pairs[j][1]) {
				dp[i] = Math.max(dp[i], dp[j] + 1);
			}
		}
	}
	return Math.max(...dp);
};

相关题目

题号	标题	题解	标签	难度	力扣
300	最长递增子序列	[✓]	数组 二分查找 动态规划	🟠	🀄️ 🔗
491	非递减子序列		位运算 数组 哈希表 1+	🟠	🀄️ 🔗
2771	构造最长非递减子数组		数组 动态规划	🟠	🀄️ 🔗