一、题目
给定两个由一些 闭区间 组成的列表，每个区间列表都是成对不相交的，并且已经排序。
返回这两个区间列表的交集。
（形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b。两个闭区间的交集是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3]。）
image.png
提示：
1、0 <= A.length < 1000
2、0 <= B.length < 1000
3、0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9
https://leetcode-cn.com/problems/interval-list-intersections/
二、解题思路
整体思路
bug free啊
纠正思路很重要
1、原有做题思路（为什么思路这么复杂）
图1
2、正确的思路
图2
自顶向下的思路：
（1）大方向：有交集、无交集
--> 代码1
（2）有交集：共同点，代码层面
--> 代码2
（3）迭代更新
图3-7
image.png
image.png
image.png
image.png
image.png
image.png
image.png
关键问题：正确的分析思路
第一步
第二步
三、题解
暴力解法
题解1:
错误解法
class Solution {
public int[][] intervalIntersection(int[][] A, int[][] B) {
int nA = A.length;
int nB = B.length;
List<int[]> res = new ArrayList<>();
int i = 0, j = 0, left = 0, right = 0;
while (i < nA && j < nB) {
if (A[i][1] < B[j][0] || A[i][0] > B[j][1]) {
// 无交集
i++;
// j++;
}else { // 有交集
left = Math.max(A[i][0], B[j][0]);
right = Math.min(A[i][1], B[j][1]);
res.add(new int[]{left, right});
if (B[j][1] < A[i][1]) {
j++;
}else {
i++;
}
}
}
return res.toArray(new int[0][]);
}
}
易错：无交集部分的指针迭代不对
正确做法：
class Solution {
public int[][] intervalIntersection(int[][] A, int[][] B) {
int nA = A.length;
int nB = B.length;
List<int[]> res = new ArrayList<>();
int i = 0, j = 0, left = 0, right = 0;
while (i < nA && j < nB) {
if (A[i][1] < B[j][0] || A[i][0] > B[j][1]) {
// 无交集
// i++;
// j++;
if (B[j][1] < A[i][1]) {
j++;
}else {
i++;
}
}else { // 有交集
left = Math.max(A[i][0], B[j][0]);
right = Math.min(A[i][1], B[j][1]);
res.add(new int[]{left, right});
if (B[j][1] < A[i][1]) {
j++;
}else {
i++;
}
}
}
return res.toArray(new int[0][]);
}
}
结果
执行用时：4 ms, 在所有 Java 提交中击败了95.25%的用户
内存消耗：40.5 MB, 在所有 Java 提交中击败了81.95%的用户
复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)
四、测试数据
[[0,2],[5,10],[13,23],[24,25]]
[[1,5],[8,12],[15,24],[25,26]]
参考
1、题解参考
https://labuladong.gitbook.io/algo/suan-fa-si-wei-xi-lie/qu-jian-jiao-ji-wen-ti
2、优秀题解
