LeetCode 986. 区间列表的交集
题目描述
题意分析
两个列表各自按区间起点递增排列，同一列表内的区间互不相交。要求返回同时属于两个列表的所有交集区间。区间是闭区间，所以只共享一个端点时，也要返回这个单点区间。
原图勘误：示例 1 的正确输出为
[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]，六项分别来自A[0]与B[0]、A[1]与B[0]、A[1]与B[1]、A[2]与B[2]、A[3]与B[2]、A[3]与B[3]。末尾两个单点不能合成[24,25]，因为两个端点之间的数不属于列表B。示例 2 的正确输出为[[2,3],[6,8]]，第二段左端点应为 6。
解法：双指针扫描两个有序区间列表
核心思路
[!blue]
用
i、j指向两个列表当前尚未处理完的区间。一个数要同时落在两个区间内，必须不小于两个左端点，也不大于两个右端点。因此交集边界为left = max(左端点)、right = min(右端点)；left <= right时交集非空，否则这两个区间没有交集。计算完当前交集后，应淘汰结束更早的区间。设第一个区间右端点为
a，第二个为b，且a < b。第二个列表内部有序且不重叠，后续区间的起点一定大于b，也就大于a，因此第一个区间不可能再与它们相交，可以安全执行i++。第二个区间还可能与第一个列表的后续区间相交，所以暂时保留。b < a时同理移动j。若
a == b，两者都不可能再与对方的后续区间相交，移动任意一侧都不会漏解。代码选择移动j；若循环继续，保留的第一个区间会在下一次比较中被淘汰。无论当前是否产生交集，都按这个右端点规则推进。每次跳过的区间都已经找完它可能产生的交集，因此不会漏掉答案。任一列表耗尽时，另一列表剩余区间也无法与已经处理完的区间再产生交集，可以直接结束；输出随指针从左到右产生，无需额外排序。
解题步骤
- 初始化
i = 0、j = 0和空结果列表。- 当两侧指针都未越界时，计算当前两个区间的
left、right。- 若
left <= right，将[left, right]加入结果；相等时也要加入。- 若第一个区间右端点更小，执行
i++；否则执行j++。- 一侧扫描完就返回结果。一开始有空列表时，循环不会进入，结果自然为空。
代码实现
class Solution {
public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
List<int[]> result = new ArrayList<>();
int i = 0;
int j = 0;
while (i < firstList.length && j < secondList.length) {
int left = Math.max(firstList[i][0], secondList[j][0]);
int right = Math.min(firstList[i][1], secondList[j][1]);
// 闭区间端点相等也产生一个单点交集。
if (left <= right) {
result.add(new int[] {
left,
right
});
}
// 结束更早的一侧不会再与另一列表的后续区间相交。
if (firstList[i][1] < secondList[j][1]) {
i++;
} else {
j++;
}
}
return result.toArray(new int[0][]);
}
}
func intervalIntersection(firstList [][]int, secondList [][]int) [][]int {
result := make([][]int, 0)
for i, j := 0, 0; i < len(firstList) && j < len(secondList); {
left := maxInt(firstList[i][0], secondList[j][0])
right := minInt(firstList[i][1], secondList[j][1])
// 闭区间端点相等也产生一个单点交集。
if left <= right {
result = append(result, []int{
left,
right,
})
}
// 结束更早的一侧不会再与另一列表的后续区间相交。
if firstList[i][1] < secondList[j][1] {
i++
} else {
j++
}
}
return result
}
func maxInt(a, b int) int {
if a > b {
return a
}
return b
}
func minInt(a, b int) int {
if a < b {
return a
}
return b
}
复杂度分析
- 时间复杂度：$O(m+n)$，其中 $m$、$n$ 是两个列表的长度。每轮至少推进一个指针，每个区间最多被指针越过一次。
- 空间复杂度：若返回 $r$ 个交集区间，结果占 $O(r+1)$ 空间。除结果外，Java 转数组前还需要 $O(r+1)$ 的临时列表引用，Go 只需要 $O(1)$ 的辅助空间。
关键点总结
[!green]
- 交集统一取较大的左端点、较小的右端点，不必区分包含、交叉或分离。
- 淘汰右端点更小的区间，依据是另一列表后续区间不可能再覆盖它。
- “有序且各自内部不相交”保证安全推进，也是线性扫描成立的前提。
易错点总结
[!yellow]
- 非空条件必须是
left <= right，写成严格小于会漏掉单点交集。- 不能按左端点决定移动哪一侧，也不能每次都同时移动两侧，否则可能跳过仍有贡献的长区间。
- 即使当前没有交集，也要推进右端点更小的一侧，不能停在原地。
- 一侧结束后不能直接追加另一侧剩余区间；题目求的是交集，剩余区间不自动属于结果。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 56. 合并区间 | 中等 | 原题计算区间并集，本题对两个有序来源求交集，区间右端较小的一侧可以先推进。 |
| 57. 插入区间 | 中等 | 同样按有序区间的边界关系分支，本题不修改输入，只输出重叠部分。 |