题目

思路

一句话：因为原列表已经有序，每个原区间相对新区间只可能落在三种位置之一——左边、重叠、右边；一次线性扫描分三段处理即可。

先想最直白的做法：把新区间塞进原列表，再按左端点排序，然后从头到尾合并重叠区间。这个思路完全正确，但浪费了题目给的“已经按左端点排好序”这个条件，多花一次 O(n log n) 的排序。

关键观察：原区间按左端点递增，所以相对新区间而言，会出现一个连续前缀“完全在左”、一个连续中段“可能与新区间重叠”、一个连续后缀“完全在右”。我们只需要：

• 左边：原区间右端点 < 新区间左端点，不可能碰，直接保留；
• 重叠：原区间左端点 ≤ 新区间右端点，合并并不断扩展新区间；
• 右边：从某个位置开始全部在原新区间之后，直接照抄。

重叠区间的“合并”就是不断取左右边界的最小值和最大值。因为一旦进入重叠段，后续的区间也可能连着叠，所以要把中段一次吃完再放入答案。

解法

用指针 i 从左往右扫一遍，ans 存结果：

1. 先把“完全在新区间左边”的区间加入答案。
2. 再处理所有“与新区间重叠”的区间，持续更新合并后的 [start, end]。
3. 把合并后的新区间加入答案。
4. 最后把“完全在新区间右边”的区间全部加入答案。

以 [[2,4],[6,8],[10,12]] 插入 [5,11] 为例：

下图把上面 4 个步骤串成流程，并逐步演示：

C++