区间合并问题概述定义区间合并指将重叠或相邻的区间合并为更大的连续区间典型应用场景日程安排、资源分配、基因组分析等核心挑战高效处理大规模区间数据并保证正确性基础算法模式排序预处理法按区间起点升序排序线性扫描并合并重叠区间时间复杂度O(n log n)主要来自排序代码模板示例def merge(intervals): intervals.sort(keylambda x: x[0]) merged [] for interval in intervals: if not merged or merged[-1][1] interval[0]: merged.append(interval) else: merged[-1][1] max(merged[-1][1], interval[1]) return merged扫描线算法将区间端点标记为开始/结束事件按坐标排序后处理事件流优势适用于离散点与区间混合场景优化策略分治与并行化将区间集分割为子问题并行处理合并子问题结果时采用多指针归并索引加速构建区间树或线段树结构支持快速查询重叠区间适用于动态区间集合场景贪心策略强化提前终止条件当剩余区间无法与当前合并结果重叠时跳出循环预处理时按区间终点排序可优化特定场景