文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
Maximum Length of Pair Chain
2. Solution
解析：Version 1，采用贪心算法，即每次都添加符合条件的、右端值最小的数值对，首先对数值对按右端值进行排序，然后将右端值最小的数值对添加到数组中，然后寻找下一个满足左端值大于数组中最后一个右端值的数值对，最后数组的长度即为最长的数值对链。每次添加右端值最小的数值对，保证了可以拼接尽可能多的数值对，Version 2只统计数值对链的个数。
- Version 1
class Solution:
def findLongestChain(self, pairs: List[List[int]]) -> int:
pairs.sort(key=lambda x: x[1])
result = []
n = len(pairs)
result.append(pairs[0])
for i in range(1, n):
if pairs[i][0] > result[-1][1]:
result.append(pairs[i])
return len(result)
- Version 2
class Solution:
def findLongestChain(self, pairs: List[List[int]]) -> int:
pairs.sort(key=lambda x: x[1])
n = len(pairs)
pre = pairs[0]
count = 1
for i in range(1, n):
if pairs[i][0] > pre[1]:
pre = pairs[i]
count += 1
return count
