LeetCode986. 区间列表的交集

本文最后更新于 484 天前，其中的信息可能已经有所发展或是发生改变。

一、思路

这个区间问题，在两个列表里，互相比较。采用双指针是实现这个过程。

分为两种情况，相交和不相交。相交情况，end取两个区间的最大值。不相交时，看哪个区间大，当前的end是小的区间的最大值。下一对start，end取大的个区间。

什么时候指针移动呢？根据两个当前区间的最大值，小的个指针就往前移。因为一直在进行两个区间的比较，所以趋向于两个指针一起往前走。

二、问题

给定两个由一些 闭区间 组成的列表，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：

代码语言：javascript复制

输入：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]]

示例 2：

代码语言：javascript复制

输入：firstList = [[1,3],[5,9]], secondList = []
输出：[]

示例 3：

代码语言：javascript复制

输入：firstList = [], secondList = [[4,8],[10,12]]
输出：[]

示例 4：

代码语言：javascript复制

输入：firstList = [[1,7]], secondList = [[3,10]]
输出：[[3,7]]

提示：

0 <= firstList.length, secondList.length <= 1000
firstList.length secondList.length >= 1
0 <= starti < endi <= 109
endi < starti 1
0 <= startj < endj <= 109
endj < startj 1