57. 插入区间
题目描述
输入区间列表 intervals，其中 intervals[i] = [starti, endi]。这些区间互不重叠，并且按 starti 从小到大排好。另给一个新区间 newInterval = [start, end]。
两个区间只要有至少一个公共点，就视为重叠。
把 newInterval 放进列表。如果它和已有区间重叠，就把这些区间合并成一个。最终列表仍须按起点升序，且区间两两不重叠。
返回处理后的区间列表。可以新建数组返回，不必原地修改 intervals。
示例 1
输入：intervals = [[1,3],[6,9]], newInterval = [2,5] 输出：[[1,5],[6,9]]
解释：[2,5] 和 [1,3] 重叠，合成 [1,5]。
示例 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] 重叠，四者合成 [3,10]。
数据范围
0 <= intervals.length <= 10^4intervals[i].length == 20 <= starti <= endi <= 10^5intervals已按starti升序排列。newInterval.length == 20 <= start <= end <= 10^5
解题思路
原列表已经有序，所以所有区间可以按与新区间的关系分成三段：完全在左边的（右端 < s）、与新区间重叠的、完全在右边的。左段原样放入结果；重叠段逐个并入 [s, e]，用 min/max 扩张边界；然后放入合并后的 [s, e]；最后原样追加右段。一次扫描就能完成，不需要重新排序。
为什么正确
第二段循环中，[s, e] 始终等于新区间与已扫描重叠区间的并集；res 中的区间始终有序且互不重叠。
复杂度分析
时间 O(n)，除结果外额外空间 O(1)。
易错点
判断重叠时端点相接也算重叠：[1,3] 与 [3,6] 要合并，所以条件是 intervals[i][0] <= e 和 intervals[i][1] < s（左段用严格小于）。另外别忘了 intervals 为空或新区间在最右边时，也要把 [s, e] 放进结果。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
res = []
s, e = newInterval
i, n = 0, len(intervals)
while i < n and intervals[i][1] < s:
res.append(intervals[i])
i += 1
while i < n and intervals[i][0] <= e:
s = min(s, intervals[i][0])
e = max(e, intervals[i][1])
i += 1
res.append([s, e])
while i < n:
res.append(intervals[i])
i += 1
return resclass Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> res = new ArrayList<>();
int s = newInterval[0], e = newInterval[1];
int i = 0, n = intervals.length;
while (i < n && intervals[i][1] < s) {
res.add(intervals[i]);
i++;
}
while (i < n && intervals[i][0] <= e) {
s = Math.min(s, intervals[i][0]);
e = Math.max(e, intervals[i][1]);
i++;
}
res.add(new int[]{s, e});
while (i < n) {
res.add(intervals[i]);
i++;
}
return res.toArray(new int[0][]);
}
}class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> res;
int s = newInterval[0], e = newInterval[1];
int i = 0, n = intervals.size();
while (i < n && intervals[i][1] < s) {
res.push_back(intervals[i]);
i++;
}
while (i < n && intervals[i][0] <= e) {
s = min(s, intervals[i][0]);
e = max(e, intervals[i][1]);
i++;
}
res.push_back({s, e});
while (i < n) {
res.push_back(intervals[i]);
i++;
}
return res;
}
};func insert(intervals [][]int, newInterval []int) [][]int {
res := [][]int{}
s, e := newInterval[0], newInterval[1]
i, n := 0, len(intervals)
for i < n && intervals[i][1] < s {
res = append(res, intervals[i])
i++
}
for i < n && intervals[i][0] <= e {
s = min(s, intervals[i][0])
e = max(e, intervals[i][1])
i++
}
res = append(res, []int{s, e})
for i < n {
res = append(res, intervals[i])
i++
}
return res
}var insert = function(intervals, newInterval) {
const res = [];
let [s, e] = newInterval;
let i = 0, n = intervals.length;
while (i < n && intervals[i][1] < s) {
res.push(intervals[i]);
i++;
}
while (i < n && intervals[i][0] <= e) {
s = Math.min(s, intervals[i][0]);
e = Math.max(e, intervals[i][1]);
i++;
}
res.push([s, e]);
while (i < n) {
res.push(intervals[i]);
i++;
}
return res;
};function insert(intervals: number[][], newInterval: number[]): number[][] {
const res: number[][] = [];
let [s, e] = newInterval;
let i = 0, n = intervals.length;
while (i < n && intervals[i][1] < s) {
res.push(intervals[i]);
i++;
}
while (i < n && intervals[i][0] <= e) {
s = Math.min(s, intervals[i][0]);
e = Math.max(e, intervals[i][1]);
i++;
}
res.push([s, e]);
while (i < n) {
res.push(intervals[i]);
i++;
}
return res;
}