给定两个由一些 闭区间 组成的列表，
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：
示例 2：
示例 3：
示例 4：
解法一：双指针 （推荐）
我们用两个指针：
i# 指向 firstList 当前区间
j# 指向 secondList 当前区间
每次只比较当前两个区间：
A = firstList[i] = [start1,end1]
B = secondList[j] = [start2,end2]
如果它们有交集，就把交集加入结果。然后移动那个结束更早的区间。
因为结束更早的区间已经不可能和对方后面的区间再产生交集了。列表是按顺序排列的，后面的区间起点只会更靠右。如果当前区间都已经结束了，它就没有继续保留的价值。
当前两个区间比较完以后，谁的右端点更小，谁就可以被安全丢弃。
对于A, B 两个闭区间，
- 它们的交集起点一定是两个起点的较大值：
lo=max(start1,start2)
- 它们的交集终点一定是两个终点的较小值：
hi=min(end1,end2)
如果lo <= hi，说明存在交集。
比如：
[1,5]和 [5,8] 的交集是 [5,5]Walk Through Example
以
firstList= [[1,4], [5,9]]，secondList= [[2,6]]为例：- 先比较
[1,4]和[2,6]， - 交集起点是
max(1,2)=2， - 终点是
min(4,6)=4， - 所以得到
[2,4]。
因为
[1,4] 结束更早，移动 firstList 的指针。- 接着比较
[5,9]和[2,6]，交集是[5,6]。
这次
[2,6] 结束更早，移动 secondList 的指针。secondList遍历结束，算法停止。
复杂度分析
设
m = len(firstList)，n = len(secondList)。- 时间复杂度：
O(m+n)
因为每次循环至少移动一个指针，每个区间最多被访问一次。
- 空间复杂度：
- 不计输出结果：
O(1) - 如果把答案数组也算入空间，最坏情况下结果数量可能达到
O(m + n)
解法二：双指针 —— 先排除不相交，再处理交集
先判断两个区间是否完全错开，即两个区间不相交。
只有两种情况：
start1 > end2# first 当前区间 完全在 second 当前区间右边
start2 > end1# second 当前区间 完全在 first 当前区间右边
如果既不是第一种，也不是第二种，就说明它们有交集。
直接计算
lo 和 hi，再判断 lo <= hi。复杂度分析
- 时间复杂度：
O(m+n)
- 空间复杂度：
- 不计输出：
O(1)
总结
这两种写法本质上都是双指针归并，区别只是交集判断方式不同。
- 解法一：
先算
lo = max(start1, start2)再算hi = min(end1, end2)如果lo <= hi，就有交集。
- 解法二：
先判断两个区间是否完全错开 （
start1 > end2或start2 > end1）； 如果没有错开，就说明有交集。
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-986-区间列表的交集
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
上一篇
[Leetcode 772] 基础计算器 III
下一篇
[Leetcode 1169] 无效交易