80.插入区间 (LeetCode 57)
插入区间 (LeetCode 57)
题目描述
给定一个无重叠且按起始端点排序的区间列表，插入一个新的区间，确保插入后的区间列表仍然有序且无重叠。
示例
- 示例 1：
输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]
- 示例 2：
输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
提示
定位插入位置：遍历原区间列表，找到第一个结束位置
>=新区间起始位置的区间合并重叠区间：继续向后遍历，直到遇到起始位置
>新区间结束位置的区间拼接结果：将未处理的前半部分 + 合并后的新区间
+未处理的后半部分组合
code
/**
* @param {number[][]} intervals
* @param {number[]} newInterval
* @return {number[][]}
*/
var insert = function (intervals, newInterval) {
// 请在此处编写代码
};
参考答案
DETAILS
function insert(intervals, newInterval) {
const res = [];
let i = 0;
const n = intervals.length;
// 添加所有结束位置 < newInterval起始位置的区间
while (i < n && intervals[i][1] < newInterval[0]) {
res.push(intervals[i++]);
}
// 合并重叠区间
while (i < n && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
res.push(newInterval);
// 添加剩余区间
while (i < n) {
res.push(intervals[i++]);
}
return res;
}