插入区间（57）

题目

给出一个无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例

输入：intervals = [[1,3],[6,9]], newInterval = [2,5] 输出：[[1,5],[6,9]]

输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] 输出：[[1,2],[3,10],[12,16]]

算法

方法一

将起始端点和结束端点分别保存在两个数组startArr和endArr中（包括newInterval的起始结束端点），并按递增排序

去除下面的情况：

• 当startArr[i]和endArr[j]为区间边界时，去除startArr中[i+1,j]的元素，去除endArr中[i,j-1]的元素，因为这个范围内的所有值不能成为区间的端点
• 当end[i]>=start[i+1]时，去除start[i+1]和end[i]，因为这个时候start[i+1]和end[i]不能成为区间的起点和终点

然后拼接每一组对应的[startArr[i], endArr[i]]成为区间，即为结果

export const insert = (intervals, newInterval) => {
  
	const startArr = [newInterval[0]],
		endArr = [newInterval[1]];

	for (let i = 0; i < intervals.length; i++) {
		startArr.push(intervals[i][0]);
		endArr.push(intervals[i][1]);
	}
	startArr.sort((a, b) => a - b);
	endArr.sort((a, b) => a - b);

	startArr.splice(
		startArr.indexOf(newInterval[0]) + 1,
		endArr.indexOf(newInterval[1]) - startArr.indexOf(newInterval[0])
	);
	endArr.splice(startArr.indexOf(newInterval[0]), endArr.indexOf(newInterval[1]) - startArr.indexOf(newInterval[0]));

	let startIndex = 1,
		endIndex = 0;
	const res = [];
	while (startIndex <= startArr.length - 1) {
		if (endArr[endIndex] >= startArr[startIndex]) {
			startArr.splice(startIndex, 1);
			endArr.splice(endIndex, 1);
		} else {
			startIndex++;
			endIndex++;
		}
	}

	for (let i = 0; i < startArr.length; i++) {
		res.push([startArr[i], endArr[i]]);
	}
	return res;
};

方法二

当intervals中的区间和newInterval没有重叠时，直接推入结果；如果有重叠，通过取最大合并区间推入结果

• 当intervals中的区间和newInterval没有重叠且都在newInterval左侧时，即intervals[i][1]<left，直接推入数组
• 当intervals中的区间和newInterval没有重叠且都在newInterval右侧时，即intervals[i][0]>right，直接推入数组
  • 此时如果placed为false，即还没有推入newInterval区间，却已经比newInterval右端点大，说明newInterval在小区间之间，直接推入结果并将placed设为true
• 除去上面两种结果，说明newInterval和小区间重叠，所以应该合并重叠区间，所以每次循环求出合并区间左侧的最小值和右侧的最大值，当循环结束时，推入结果

export const insert = (intervals, newInterval) => {
	let left = newInterval[0],
		right = newInterval[1];
	let placed = false;
	const res = [];
	for (let i = 0; i < intervals.length; i++) {
		if (intervals[i][1] < left) {
			res.push(intervals[i]);
		} else if (intervals[i][0] > right) {
			if (!placed) {
				res.push([left, right]);
				placed = true;
			}
			res.push(intervals[i]);
		} else {
			left = Math.min(intervals[i][0], left);
			right = Math.max(intervals[i][1], right);
		}
	}
	if (!placed) {
		res.push([left, right]);
	}
	return res;
};