题目描述
给出一个无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 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] 重叠。
来源：LeetCode
思路
先找到每个点所落在的区间，如果不落在已有区间内，找到落在的区间间隔。然后根据新区间的左右端点，和所落在的区间的情况，确定一个合并区间，并把新区间落下所影响到的原区间全部移除。
为了提高找到落点区间的效率，这里可以使用二分法查找，我使用了之后发现运行耗时反而长了。不得不吐槽，测试用例不够强很吃亏。
需要注意的点：
- 左端点若落在区间内，需要多移除一个区间。
- 左端若不落在区间内，需要将移除起点后移一位。
解法
/**
* @desc 二分法找到值落在的区间或落在的区间后
* @returns {index, in} index为最接近的区间下标，向左靠齐，in标记在区间内还是外
*/
const findPosition = (intervals, val) => {
let left = 0;
let right = intervals.length;
let middle = ~~((left + right) / 2);
while (!(middle === left || middle === right)) {
if (intervals[middle][0] <= val) {
left = middle;
} else {
right = middle;
}
middle = ~~((left + right) / 2);
}
if (middle < intervals.length && val < intervals[middle][0]) {
middle -= 1;
}
return { index: middle, in: Boolean(intervals[middle] && val <= intervals[middle][1]) };
};
/**
* @param {number[][]} intervals
* @param {number[]} newInterval
* @return {number[][]}
*/
const insert = (intervals, newInterval) => {
const left = findPosition(intervals, newInterval[0]);
const right = findPosition(intervals, newInterval[1]);
// 新区间落下后，影响到的原先区间数目，都要去除
const removeCount = right.index - left.index + Number(left.in);
// 去除的区间们的起点
const removeStart = left.index + Number(!left.in);
intervals.splice(removeStart, removeCount, [
left.in ? intervals[left.index][0] : newInterval[0],
right.in ? intervals[right.index][1] : newInterval[1],
]);
return intervals;
};