81.区间列表的交集 (LeetCode 986)
区间列表的交集 (LeetCode 986)
题目描述
给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。
示例：
- 示例 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]]
提示：
双指针遍历：用指针分别扫描两个区间列表
求交集条件：两个区间存在重叠的条件为
a_end >= b_start 且 b_end >= a_start移动指针策略：保留结束位置较晚的区间，移动结束较早的区间的指针
code
/**
* @param {number[][]} firstList
* @param {number[][]} secondList
* @return {number[][]}
*/
var intervalIntersection = function (firstList, secondList) {
// 请在此处编写代码
};
参考答案
DETAILS
/**
* @param {number[][]} firstList
* @param {number[][]} secondList
* @return {number[][]}
*/
var intervalIntersection = function (firstList, secondList) {
const res = [];
let i = 0,
j = 0;
while (i < firstList.length && j < secondList.length) {
const a_start = firstList[i][0],
a_end = firstList[i][1],
b_start = secondList[j][0],
b_end = secondList[j][1];
if (a_end >= b_start && b_end >= a_start) {
res.push([Math.max(a_start, b_start), Math.min(a_end, b_end)]);
}
if (a_end < b_end) {
i++;
} else {
j++;
}
}
return res;
};