难度: Medium
给你一个由 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.length1 <= n <= 1000-1000 <= lefti < righti <= 1000运行时间: 54 ms
内存: 16.5 MB
class Solution:
def findLongestChain(self, pairs: List[List[int]]) -> int:
pairs = sorted(pairs, key=lambda x : (x[1], -x[0]))
cnt = 1
last = pairs[0][1]
for i in range(1, len(pairs)):
if pairs[i][0] > last:
cnt += 1
last = pairs[i][1]
return cnt
此题解采用了贪心算法。首先，对输入的数对数组按照每个数对的第二个元素升序排序，如果第二个元素相同，则按第一个元素降序排序。这样可以优先处理右端点较小的数对，以便使得后续有更多的可能数对可以接上去。初始化一个计数器 cnt 和变量 last，分别用来记录最长链的长度和上一个数对的右端点。遍历排序后的数对，只有当当前数对的左端点大于 last 时，才能将其加入到当前的数对链中，此时更新 cnt 和 last。最后返回 cnt，即为最长数对链的长度。
时间复杂度: O(n log n)
空间复杂度: O(1)
class Solution:
def findLongestChain(self, pairs: List[List[int]]) -> int:
# 对数对按右端点升序排序，右端点相同则按左端点降序排序
pairs = sorted(pairs, key=lambda x: (x[1], -x[0]))
cnt = 1 # 初始化链长度
last = pairs[0][1] # 上一个数对的右端点
for i in range(1, len(pairs)):
if pairs[i][0] > last:
cnt += 1 # 找到可连接的新数对，链长度增加
last = pairs[i][1] # 更新最新的数对右端点
return cnt # 返回最长链的长度
在排序数对时，选择按第二个元素进行升序排序是为了尽可能地让数对链的右端点小，这样后续在添加新的数对时有更大的空间和更多的选择。这种排序方式有助于尽快完成数对的连接，减少被排除的可能性。当第二个元素相同时，按第一个元素降序排序则有助于在相同的结束点中选择开始点较大的数对，这样做可以减少后续数对的连接冲突，因为更早开始的数对可能阻碍后续数对的加入。
题解中采用的贪心策略基于“最优子结构”的直觉，即在每一步选择当前最优的决策将导致全局最优的解决方案。具体到这个问题，每次选择右端点最小的数对，可以最大化后续添加更多数对的可能性，从而延长数对链。这种策略有效的原因是，每次扩展链时保证不会有更好的选择来替代当前的数对而导致错过更长的链，因为更长的右端点会减少未来连接数对的机会。
算法仍然可以正确运行，即使存在重复的数对。在排序和遍历的过程中，重复的数对会被视为独立的个体。在贪心策略下，尽管重复数对可能会被多次考虑，但是它们的处理不会影响最终结果的正确性，因为每个数对都是基于其左端点和右端点来决定是否加入到当前链中。不需要特别的处理来去除或区分这些重复数对，因为它们在排序和选择中自然会被适当处理。
初始化cnt为1而不是0的原因是至少存在一个数对会被加入到数对链中（假设输入的数对数组非空）。因此，从第一个数对开始，链已经有一个元素了。这是一种计数的开始方法，保证计数从实际的数对数量开始，而不是从0开始，后者需要在添加第一个数对时特别将计数器增加。这样的初始化简化了逻辑，使得后续只需在找到新的可连接数对时增加计数器即可。