友情支持
如果您觉得这个笔记对您有所帮助,看在D瓜哥码这么多字的辛苦上,请友情支持一下,D瓜哥感激不尽,😜
有些打赏的朋友希望可以加个好友,欢迎关注D 瓜哥的微信公众号,这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi 。因为众所周知的原因,有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
986. 区间列表的交集
给定两个由一些 闭区间 组成的列表,firstList
和 secondList
,其中 firstList[i] = [starti, endi]
而 secondList[j] = [startj, endj]
。每个区间列表都是成对 不相交 的,并且 已经排序 。
返回这 两个区间列表的交集 。
形式上,闭区间 [a, b]
(其中 a <= b
)表示实数 x
的集合,而 a <= x <= b
。
两个闭区间的 *交集*是一组实数,要么为空集,要么为闭区间。例如,[1, 3]
和 [2, 4]
的交集为 [2, 3]
。
示例 1:


输入:firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]] 输出:[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
示例 2:
输入:firstList = [[1,3],[5,9]], secondList = [] 输出:[]
示例 3:
输入:firstList = [], secondList = [[4,8],[10,12]] 输出:[]
示例 4:
输入:firstList = [[1,7]], secondList = [[3,10]] 输出:[[3,7]]
提示:
-
0 <= firstList.length, secondList.length <= 1000
-
firstList.length + secondList.length >= 1
-
0 <= starti < endi <= 109
-
endi < starti+1
-
0 <= startj < endj <= 109
-
endj < startj+1
思路分析
双指针。先排除两种没有交集的情况,剩下四种有交集的情况,左边选两个里面最大的,右边选两个里面最小的。哪个小,向右移动哪个的指针。
官方题解代码更简洁,直接左边选两个里面最大的,右边选两个里面最小的。然后再检查这两个值是否左小右大。也是“哪个小,向右移动哪个的指针。”。

-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-06-03 14:23:09
*/
public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
if (firstList == null || secondList == null
|| firstList.length == 0 || secondList.length == 0) {
return new int[0][0];
}
int first = 0, second = 0;
List<int[]> result = new ArrayList<>();
while (first < firstList.length && second < secondList.length) {
if (firstList[first][1] < secondList[second][0]) {
first++;
} else if (secondList[second][1] < firstList[first][0]) {
second++;
} else {
int max = Math.max(firstList[first][0], secondList[second][0]);
int min;
if (firstList[first][1] > secondList[second][1]) {
min = secondList[second][1];
second++;
} else {
min = firstList[first][1];
first++;
}
result.add(new int[]{max, min});
}
}
return result.toArray(new int[][]{});
}