区间插入算法 题目描述：给定一组无重叠的区间（按照起始端点排序），以及一个待插入的新区间。你需要将这个新区间插入到原有区间集合中，并在必要时合并重叠的区间，使得结果区间集合仍然无重叠且有序。 循序渐进讲解： 问题理解 输入是已排序且无重叠的区间列表，例如 intervals = [ [ 1,3],[ 6,9] ] 新区间 newInterval = [ 2,5 ] 需要插入 可能出现重叠（如新区间与[ 1,3]重叠），需要合并成[ 1,5 ] 最终输出应保持排序且无重叠：[ [ 1,5],[ 6,9] ] 关键思路分析 新区间可能： 完全在某个区间左侧（无重叠） 与一个或多个区间重叠（需要合并） 完全在某个区间右侧（无重叠） 核心是找到新区间与已有区间的所有重叠部分 具体步骤实现 （1）初始化空结果列表result，索引i=0 （2）遍历所有区间，将完全在新区间左侧的区间直接加入结果 即 intervals[ i].end < newInterval.start 例如[ 1,3]的end=3 < newInterval.start=2？不成立，停止 （3）合并重叠区间： 此时intervals[ i ]可能与新区间重叠 计算合并后的区间： start = min(newInterval.start, 当前区间.start) end = max(newInterval.end, 当前区间.end) 继续检查后续区间是否还与这个合并区间重叠 示例：合并[ 1,3]和[ 2,5]得到[ 1,5 ] （4）将合并后的区间加入结果 （5）将剩余未处理的区间（完全在新区间右侧）加入结果 完整示例演示 输入：intervals = [ [ 1,2],[ 3,5],[ 6,7],[ 8,10],[ 12,16]], newInterval = [ 4,8 ] 步骤： [ 1,2]在[ 4,8]左侧 → 加入结果：[ [ 1,2] ] [ 3,5]与[ 4,8 ]重叠 → 合并：start=min(3,4)=3, end=max(5,8)=8 [ 6,7]与合并区间[ 3,8 ]重叠 → 继续合并：end=max(8,7)=8 [ 8,10]与[ 3,8 ]重叠（因8=8）→ 合并：end=max(8,10)=10 [ 12,16]在[ 3,10 ]右侧 → 最后加入 结果：[ [ 1,2],[ 3,10],[ 12,16] ] 算法特点总结 时间复杂度O(n)，只需遍历一次 空间复杂度O(n)，存储结果 关键点在于正确处理重叠判断和动态合并