插入区间
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给你一个无重叠的、按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。
如果两个区间 至少 共享一个点，则认为它们是重叠的。
在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。
返回插入之后的 intervals。
注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。
示例 1
示例 2
模拟答题者思考
1. 最直接：把 newInterval 插入 intervals 合适位置，再调用上一题「合并区间」的排序+扫描——可行但多了一次 O(n log n) 排序，而本题输入已经有序，浪费了结构信息。
2. 重复在哪里？合并区间需要排序是因为输入乱序；本题 intervals 已按起点升序且无重叠，插入只需一次线性扫描，按与 newInterval 的相对位置分三段处理。
3. 关键转化：三阶段扫描——(1) 所有终点 < newInterval[0] 的区间直接入 ans；(2) 所有与 newInterval 重叠的区间不断扩展 newInterval 的左右端点；(3) 将合并后的 newInterval 入 ans，再把剩余区间依次 append。
4. 重叠判定：因 intervals 有序，阶段二条件为 intervals[i][0] <= newInterval[1]（新区间右端点尚未被当前区间起点越过）。注意端点相接算重叠，与合并区间题一致。
5. 复杂度：每个区间访问一次，O(n) 时间、O(n) 输出空间——比「插入后重排+合并」更优。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
intervals | list<list<int>> | 定义：已按起点升序、两两不重叠的区间列表 维护：从左到右线性扫描，用指针 i 标记当前考察位置，不回溯更新：每轮根据与 newInterval 的位置关系，将区间归入「左侧无重叠 / 待合并 / 右侧无重叠」三类之一 |
newInterval | list<int> | 定义：待插入的新区间 [start, end]维护：在合并阶段不断扩展左右端点，直到与所有重叠区间融合成一块 更新： newInterval[0] = min(newInterval[0], intervals[i][0])；newInterval[1] = max(newInterval[1], intervals[i][1]) |
ans | list<list<int>> | 定义：插入并合并后的结果区间列表 维护：始终按起点递增，且相邻区间互不相交 更新：阶段一 append 左侧区间；阶段二结束后 append 合并后的 newInterval；阶段三 append 剩余右侧区间 |
i | int | 定义：扫描 intervals 的下标指针维护：单调递增，每个区间最多访问一次 更新：每处理完一个区间 i += 1；三阶段共用同一指针，自然衔接 |
落码步骤
1. 初始化 ans = []，i = 0，n = len(intervals)
2. 阶段一：当 i < n 且 intervals[i][1] < newInterval[0]，将 intervals[i] 加入 ans，i += 1
3. 阶段二：当 i < n 且 intervals[i][0] <= newInterval[1]，合并：newInterval[0] = min(...)，newInterval[1] = max(...)，i += 1
4. 将合并后的 newInterval 加入 ans
5. 阶段三：将 intervals[i:] 剩余区间依次加入 ans
6. 返回 ans（若 intervals 为空，阶段一、二跳过，直接返回 [newInterval]）
代码实现
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
ans = []
i, n = 0, len(intervals)
# 阶段一：完全在 newInterval 左侧的区间
while i < n and intervals[i][1] < newInterval[0]:
ans.append(intervals[i])
i += 1
# 阶段二：与 newInterval 重叠，不断扩展
while i < n and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
ans.append(newInterval)
# 阶段三：剩余右侧区间
while i < n:
ans.append(intervals[i])
i += 1
return ansclass Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> ans;
int i = 0, n = intervals.size();
// 阶段一：完全在 newInterval 左侧
while (i < n && intervals[i][1] < newInterval[0]) {
ans.push_back(intervals[i]);
i++;
}
// 阶段二：重叠合并
while (i < n && intervals[i][0] <= newInterval[1]) {
newInterval[0] = min(newInterval[0], intervals[i][0]);
newInterval[1] = max(newInterval[1], intervals[i][1]);
i++;
}
ans.push_back(newInterval);
// 阶段三：剩余右侧
while (i < n) {
ans.push_back(intervals[i]);
i++;
}
return ans;
}
};
// 时间 O(n)，空间 O(n)（输出数组）复杂度分析
O(n)
O(n)（输出数组，不计输入）
常见坑
阶段一条件写成 <=：应为 intervals[i][1] < newInterval[0]，若用 <= 会把端点相接的区间错误地留在阶段一而不合并（如 [1,3] 与 [3,5]）。
阶段二条件写成 <：应为 intervals[i][0] <= newInterval[1]，否则端点相接（如 newInterval=[4,8] 与 [8,10]）无法合并。
忘记在阶段二结束后 append newInterval：合并后的新区间必须显式入 ans，否则结果缺少插入块。
必测边界 Case
intervals = [], newInterval = [5,7] → [[5,7]]（直接返回新区间）
intervals = [[3,5],[12,15]], newInterval = [1,2] → [[1,2],[3,5],[12,15]]（阶段一无元素，不合并，直接 append 后接原列表）
intervals = [[1,2],[3,5]], newInterval = [6,8] → [[1,2],[3,5],[6,8]]（阶段二无重叠，append 新区间后阶段三为空）
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] → [[1,2],[3,10],[12,16]]（阶段二循环多次扩展）
intervals = [[3,5]], newInterval = [1,10] → [[1,10]]（合并后新区间吞掉原区间）