友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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
思路分析
贪心算法。尽可能减小结尾数值，提高增加长度的可能性。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-04-18 22:38:26
*/
public int findLongestChain(int[][] pairs) {
Arrays.sort(pairs, Comparator.comparingInt((int[] a) -> a[0])
.thenComparingInt(a -> a[1]));
int result = 1;
int index = 0;
for (int i = 1; i < pairs.length; i++) {
int[] h = pairs[index];
int[] t = pairs[i];
if (h[1] < t[0]) {
index = i;
result++;
// 减小结尾数值，提高增加长度的可能性
} else if (h[0] <= t[0] && t[1] < h[1]) {
index = i;
}
}
return result;
}