Meta OA 面试真题解析：Interval Insertion 区间插入与合并

Interval Insertion

You are given a set of non-overlapping intervals sorted by their start times, and another interval to insert. Insert the new interval into the set and merge any overlapping intervals.

Example:

Input:
[[1,2], [3,9]]
[[4,6], [8,10], [11,12]]

Output should be:
[[1,2], [3,10], [11,12]]

这道题考察区间插入与合并：给定按起点排序且互不重叠的区间集合，再插入一个新区间后，需要把所有发生重叠的区间合并成一个更大的区间。常见做法是按顺序扫描，先保留完全在新区间左侧的区间，再处理与新区间重叠的部分并不断扩展边界，最后补上右侧剩余区间。核心数据结构只需要数组和线性遍历，重点是正确处理边界相交与连续重叠的情况。