LeetCode 986. 区间列表的交集
目录
题目描述
题意分析
输入是两个区间列表，每个列表内部已经按起点升序排好，而且同一个列表里的区间两两不相交。要输出的是两个列表所有区间的公共部分，也就是每一段同时被两边覆盖的闭区间。
「闭区间」是最容易被忽略的约束。
[1,2]和[2,3]共享端点2，按题意算作交集[2,2]，而不是没有交集，所以判定条件必须允许左右端点相等。「各自有序且不重叠」是另一个强信号。它意味着两边都能从左往右单向推进，既不需要先排序，也不需要处理同一列表内部相互覆盖的情况。
边界情况：任意一个列表为空；两个区间完全错开；一个区间被另一个完全包住；交集退化成一个点。
解法：双指针扫描两个有序区间列表
核心思路
两个闭区间
[a, b]、[c, d]的交集只能是[max(a, c), min(b, d)]。令left = max(a, c)、right = min(b, d)，当且仅当left <= right时交集非空；等号成立时得到单点区间，也必须保留。两个列表各自有序且内部不重叠，因此不必枚举所有区间对。用
i、j指向当前区间，求完交集后淘汰右端点更小的区间：它已经结束，而另一列表后续区间的起点只会更靠右，它不可能再产生新交集。循环不变量是：下标小于
i、j的区间已经贡献完所有可能交集。每轮至少有一个指针右移，所以整体是线性扫描。
解题步骤
- 初始化双指针
i = 0、j = 0。- 计算当前两个区间的交集边界
left、right。- 若
left <= right，把[left, right]加入答案。- 右端点较小的一侧不可能再与后续区间相交，移动该侧指针；右端点相等时移动任意一侧都正确。
- 任一列表扫描结束后返回结果。
例如
[5,10]与[1,5]的交集是[5,5]。随后[1,5]结束得更早，移动它所在列表的指针，而[5,10]仍可能与下一个区间相交。
代码实现
import java.util.ArrayList;
import java.util.List;
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)$，两个指针都只向右移动一次。
- 空间复杂度：$O(1)$，不计返回结果，仅使用常数个变量。
关键点总结
- 交集统一写成
[max(左端点), min(右端点)]，无需分类讨论包含或交叉。- 闭区间的非空条件是
left <= right，相等时也是合法交集。- 移动的是右端点更小的一侧，因为它已经不可能参与后续交集。
- 线性扫描成立依赖“各列表有序且内部不重叠”；若条件取消，应先分别合并区间。
易错点总结
- 把
left <= right写成left < right，会漏掉[2,2]这样的单点交集。- 按左端点决定移动哪一侧没有淘汰依据，可能跳过仍有贡献的长区间。
- 某一侧结束后不要把另一侧剩余区间直接加入答案，它们没有配对区间。
- 输出顺序无需额外排序；双指针产生的交集天然按起点递增。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 56. 合并区间 | 中等 | 排序后合并重叠区间 |
| 57. 插入区间 | 中等 | 有序区间中插入并合并 |
| 435. 无重叠区间 | 中等 | 按右端点贪心选区间 |
| 1229. 安排会议日程 | 中等 | 双指针找首个足够长的公共空闲段 |
| 1288. 删除被覆盖区间 | 中等 | 区间覆盖关系判定 |