46 lines
1.4 KiB
JavaScript
46 lines
1.4 KiB
JavaScript
/**
|
||
* http://leetcode.cn/problems/insert-interval/?envType=study-plan-v2&envId=top-interview-150
|
||
* @param {number[][]} intervals
|
||
* @param {number[]} newInterval
|
||
* @return {number[][]}
|
||
*/
|
||
const insert = function (intervals, newInterval) {
|
||
|
||
};
|
||
|
||
/*
|
||
假设我们插入的区间是[left, right]，[start, end]表示当前元素的左右区间，由于intervals的所有区间都是
|
||
按照左区间排序的，当end小于left时表明新插入的区间和当前区间没有重合，没必要合并，就把当前区间存入result
|
||
如果，当start大于right时表明这两个区间没有重合也不需要合并，其他情况需要合并区间，合并的区间为[min(start,left), max(end, right)]
|
||
*/
|
||
|
||
function f1(intervals, newInterval) {
|
||
const result = [];
|
||
let i = 0;
|
||
const n = intervals.length;
|
||
|
||
// 1. 插入所有与 newInterval 不重叠的区间
|
||
while (i < n && intervals[i][1] < newInterval[0]) {
|
||
result.push(intervals[i]);
|
||
i++;
|
||
}
|
||
|
||
// 2. 合并重叠的区间
|
||
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++;
|
||
}
|
||
|
||
// 3. 将合并后的 newInterval 插入到结果中
|
||
result.push(newInterval);
|
||
|
||
// 4. 插入剩余的所有区间
|
||
while (i < n) {
|
||
result.push(intervals[i]);
|
||
i++;
|
||
}
|
||
|
||
return result;
|
||
}
|