986. 区间列表的交集
题目描述
输入两个闭区间列表 firstList 和 secondList，每个区间写成 [start, end]，表示满足 start <= x <= end 的所有实数 x。
同一个列表内的区间互不相交，并且按起点从小到大排列。任一列表都可能为空。
两个闭区间的交集要么为空，要么仍是一个闭区间，例如 [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]]
解释：逐对求交，例如 [0,2] 与 [1,5] 得到 [1,2]，[5,10] 与 [1,5] 只在 5 处相交得到 [5,5]。
示例 2
输入：firstList = [[1,3],[5,9]], secondList = [] 输出：[]
解释：secondList 为空，所以没有交集。
数据范围
0 <= firstList.length, secondList.length <= 1000firstList.length + secondList.length >= 10 <= starti < endi <= 10^9endi < starti+1（即每个区间的终点小于同列表下一个区间的起点）0 <= startj < endj <= 10^9endj < startj+1（同上）
解题思路
i、j 分别指向两个列表的当前区间。两区间的交集是 [max(起点), min(终点)]，只要 lo <= hi 就记下。然后看谁的终点更早：终点更早的那个区间不可能再与对方后面的区间相交（对方后面的区间起点都在对方当前终点之后，而它已经结束），所以把它的指针后移。
为什么正确
firstList[..i-1] 与 secondList[..j-1] 中的区间，已经和所有可能相交的对方区间比较过，它们贡献的交集都已按顺序写入 ans。
复杂度分析
时间 O(m + n)，每轮恰好移动一个指针；结果之外的额外空间 O(1)。
易错点
移动指针要看终点而不是起点；终点相等时移动任意一个都可以。区间是闭区间，lo == hi 也是合法交集（例如 [5,5]），判断条件要写 lo <= hi。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
ans = []
i = j = 0
while i < len(firstList) and j < len(secondList):
lo = max(firstList[i][0], secondList[j][0])
hi = min(firstList[i][1], secondList[j][1])
if lo <= hi:
ans.append([lo, hi])
if firstList[i][1] < secondList[j][1]:
i += 1
else:
j += 1
return ansclass Solution {
public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
List<int[]> ans = new ArrayList<>();
int i = 0, j = 0;
while (i < firstList.length && j < secondList.length) {
int lo = Math.max(firstList[i][0], secondList[j][0]);
int hi = Math.min(firstList[i][1], secondList[j][1]);
if (lo <= hi) {
ans.add(new int[]{lo, hi});
}
if (firstList[i][1] < secondList[j][1]) {
i++;
} else {
j++;
}
}
return ans.toArray(new int[0][]);
}
}class Solution {
public:
vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {
vector<vector<int>> ans;
int i = 0, j = 0;
while (i < firstList.size() && j < secondList.size()) {
int lo = max(firstList[i][0], secondList[j][0]);
int hi = min(firstList[i][1], secondList[j][1]);
if (lo <= hi) {
ans.push_back({lo, hi});
}
if (firstList[i][1] < secondList[j][1]) {
i++;
} else {
j++;
}
}
return ans;
}
};func intervalIntersection(firstList [][]int, secondList [][]int) [][]int {
ans := [][]int{}
i, j := 0, 0
for i < len(firstList) && j < len(secondList) {
lo := max(firstList[i][0], secondList[j][0])
hi := min(firstList[i][1], secondList[j][1])
if lo <= hi {
ans = append(ans, []int{lo, hi})
}
if firstList[i][1] < secondList[j][1] {
i++
} else {
j++
}
}
return ans
}var intervalIntersection = function(firstList, secondList) {
const ans = [];
let i = 0, j = 0;
while (i < firstList.length && j < secondList.length) {
const lo = Math.max(firstList[i][0], secondList[j][0]);
const hi = Math.min(firstList[i][1], secondList[j][1]);
if (lo <= hi) {
ans.push([lo, hi]);
}
if (firstList[i][1] < secondList[j][1]) {
i++;
} else {
j++;
}
}
return ans;
};function intervalIntersection(firstList: number[][], secondList: number[][]): number[][] {
const ans = [];
let i = 0, j = 0;
while (i < firstList.length && j < secondList.length) {
const lo = Math.max(firstList[i][0], secondList[j][0]);
const hi = Math.min(firstList[i][1], secondList[j][1]);
if (lo <= hi) {
ans.push([lo, hi]);
}
if (firstList[i][1] < secondList[j][1]) {
i++;
} else {
j++;
}
}
return ans;
}