友情支持
如果您觉得这个笔记对您有所帮助，看在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[][]{});
}