最长数对链（最长递增对序列）
题目描述
给你一个由 n 个数对组成的数组 pairs，其中 pairs[i] = [left_i, right_i]，并且 left_i < right_i。
我们定义链为一系列数对 (p1, p2, …, pk)，满足对于所有 1 <= i < k 都有 right_i < left_{i+1}。
求可以从给定数对中形成的最长链的长度。
注意：
- 你可以以任意顺序选择数对，不要求按照原始顺序。
- 数对可以任意排序后再选择，只要满足链的条件即可。
- 一个常见简化条件：题目保证数对中
left_i < right_i，但不保证数对之间无重叠。
解题思路
这实际上是最长递增子序列的一个二维变种，只不过比较的条件是“第二个数小于下一个的第一个数”。
我们可以用动态规划来解，步骤是：
-
排序：为了让选择数对时有顺序可循，我们先按每个数对的第一个元素升序排序。
这样我们只需要往后看，不需要往前看，因为后面的数对的起始点一定不小于前面的起始点（排序后）。 -
状态定义：
定义dp[i]表示以第 i 个数对为结尾的最长链的长度（排序后的索引 i）。 -
状态转移：
对于数对 i，我们要看前面所有的数对 j（j < i），如果pairs[j][1] < pairs[i][0]，说明 j 可以接在 i 之前，那么：dp[i] = max(dp[i], dp[j] + 1)否则，不能接，那么
dp[i]至少是 1（只选自己）。 -
初始条件：
一开始每个数对自身可以作为一个长度为 1 的链，所以dp[i] = 1对所有 i 成立。 -
结果：
最终答案是max(dp[0..n-1])。
举例说明
假设数对为：
pairs = [[1,2], [2,3], [3,4]]
- 排序（已经按第一维升序，不用动）。
- 初始化
dp = [1, 1, 1]。 - 对 i=1（
[2,3]）：- 看 j=0（
[1,2]），2 < 2吗？不成立，因为要严格小于，所以不能接。 - 所以
dp[1]还是 1。
- 看 j=0（
- 对 i=2（
[3,4]）：- 看 j=0（
[1,2]），2 < 3✅，dp[2] = max(1, dp[0]+1=2) = 2 - 看 j=1（
[2,3]），3 < 3❌，不更新
- 看 j=0（
- 最终 dp = [1, 1, 2]，最大值 2，最长链是
[1,2] -> [3,4]，长度为 2。
但实际上这里有更优的选择：[1,2] -> [3,4] 已经是最长了。
如果例子是 [[1,2],[7,8],[4,5]]，排序后是 [1,2],[4,5],[7,8]，可以全部接起来，长度 3。
更高效的解法（贪心）
这个问题其实是区间调度问题的变种，可以用贪心解决：
- 按每个数对的第二个元素升序排序（类似安排最多不重叠区间，但这里不要求区间不重叠，只要求链中前一个的右端 < 后一个的左端）。
- 贪心地选：记录当前链的最后一个数对的右端点
end，遍历排序后的数对，如果当前数对的左端 > 上一个选的右端，就选它，并更新end。
贪心正确性证明：
因为按右端点排序后，每次选结束最早的，给后面留下更多空间，可以得到最长链。这实际上就是最长不重叠区间个数的类似思路，但这里是“严格小于”条件，本质相同。
贪心解法步骤
输入：pairs = [[1,2], [2,3], [3,4]]
- 按第二维排序：
[1,2], [2,3], [3,4]（已经有序）。 - 初始化：
end = -∞，count = 0。 - 遍历：
[1,2]：左端 1 > end（-∞）✅，选，count=1，end=2[2,3]：左端 2 > end（2）❌，不选[3,4]：左端 3 > end（2）✅，选，count=2，end=4
- 结果：
count=2。
对比两种方法
- 动态规划：O(n²) 时间，O(n) 空间，通用性强，容易理解。
- 贪心：O(n log n) 时间（排序），O(1) 空间，效率更高，但需要理解正确性。
在实际做题时，如果题目明确是最长数对链，通常用贪心（按右端点排序）更优。
但如果是更复杂的情况（比如每个数对有权重，求最大权重链），则必须用动态规划。