646. 最长数对链

题目描述：

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

---

解题分析及思路：

方法：排序 + 贪心

思路：

首先，对数对按照第二个数字 b 进行升序排序。如果 b 相同，则按第一个数字 a 进行升序排序。这一步的目的是为了尽可能让每次选择的数对都能为后续的选择留出更多空间，方便形成更长的链。

排序后，数对链的末尾的数字 b 会尽可能小，这样可以尽可能地为下一个数对留出更多的选择余地。

通过遍历排序后的数对列表，我们采用贪心的思想，逐个判断当前数对是否可以加入到数对链中。

初始时，设定一个变量 cur 表示当前链的末尾数字，初始值为负无穷。每次遍历到一个新的数对 (a, b) 时，如果 a > cur，表示当前数对可以接入链中，此时更新 cur = b 并将链的长度 length 加 1。

func findLongestChain(pairs [][]int) (res int) {
	sort.Slice(pairs, func(i, j int) bool {
		return pairs[i][1] < pairs[j][1]
	})
	cur := math.MinInt32
	for index := range pairs {
		if pairs[index][0] > cur {
			cur = pairs[index][1]
			res++
		}
	}
	return
}

复杂度：

• 时间复杂度：O(n * log n)
• 空间复杂度：O(1)

执行结果：

• 执行耗时:24 ms,击败了69.86% 的Go用户
• 内存消耗:6.2 MB,击败了97.26% 的Go用户