- 正确答案：合并多个区间的核心步骤是先按区间的起始位置升序排序，然后遍历排序后的区间，维护一个当前合并区间 [start, end]；对于每个新区间 [a, b]，若 a <= current_end，则可合并（更新 current_end = max(current_end, b)）；否则将当前合并区间加入结果，并以 [a, b] 作为新的当前区间。最终返回所有合并后的不重叠区间。 - 解答思路：第一步：理解“合并”的定义——两个区间 [a,b] 和 [c,d] 可合并当且仅当它们相交或相邻（常见题设要求“重叠即合并”，相邻如 [1,3] 和 [3,6] 是否合并需看题目定义；标准 LeetCode 56 题只要求重叠/覆盖即合并，即 c <= b 即可合并）。第二步：观察发现，若区间无序，每次插入都要扫描全部已合并区间，时间复杂度高；而排序后只需单次线性扫描，因为后续区间起始点单调递增，一旦新区间左端点超过当前合并区间的右端点，就不可能再与之前任何区间重叠（由排序保证）。第三步：贪心策略成立——排序后，能和当前区间合并的，一定在连续前缀中；跳过合并即意味着分界点，这是最优子结构+贪心选择性质的体现。第四步：实现时注意边界处理：空输入、单区间、全重叠、完全分离等 corner case。 - 深度知识讲解：本题本质考察对区间几何关系的形式化建模能力、排序预处理的算法设计意识、以及贪心正确性的理解。底层涉及的关键知识点包括：（1）比较器设计与稳定排序：区间排序需自定义比较逻辑（按 start 升序；若 start 相同，按 end 升序更鲁棒，避免因 end 乱序导致误判，例如 [[1,4],[1,3]] 若不按 end 排，虽不影响合并结果，但增强代码健壮性）。Java 中需实现 Comparator；C++ 用 lambda；Python 可用 sorted(intervals, key=lambda x: (x[0], x[1]))。（2）区间重叠判定的数学本质：两闭区间 [a,b] 和 [c,d] 重叠 ⇔ max(a,c) <= min(b,d)。但实际编码中采用更高效判定：已知 a <= c（因已排序），则重叠条件简化为 c <= b。该简化依赖于排序前提，体现了“预处理改变问题结构”的算法思想。（3）时间复杂度分析：排序 O(n log n)，扫描 O(n)，总体 O(n log n)；空间复杂度 O(1)（不计输出数组），属于原地合并的典型范式。（4）稳定性与正确性证明：贪心选择性质——每次将当前能合并的最长连续区间一次性合并，不会导致后续遗漏。反证：假设存在更优解，在某步未合并本可合并的区间 [c,d]（c<=b），则其必被后面某个区间 [e,f] 合并，但 e >= c（排序），故 e <= b 才可能与前面区间连通，矛盾。因此贪心安全。（5）扩展场景：若区间为开区间、半开区间，重叠判定需调整（如 (1,3) 和 (3,5) 不重叠）；若需支持动态插入区间（在线合并），应使用区间树（Interval Tree）或平衡 BST 维护，支持 O(log n) 插入与合并查询；若数据量极大（如磁盘外存），需考虑分块排序+归并合并（external merge）。 - 伪代码（带详细注释）： ``` function merge(intervals): if intervals is empty: return [] // 步骤1：按起点升序排序；起点相同时按终点升序（提升鲁棒性） sort intervals by (interval[0], interval[1]) merged = [] current_start = intervals[0][0] current_end = intervals[0][1] // 步骤2：线性扫描合并 for i from 1 to length(intervals)-1: interval = intervals[i] start = interval[0] end = interval[1] // 判定是否重叠：已排序 ⇒ start >= current_start，只需检查 start <= current_end if start <= current_end: // 可合并：扩展当前区间的右边界（取最大值，因可能存在 [1,5] 和 [2,3]） current_end = max(current_end, end) else: // 不重叠：保存当前合并区间，并重置为新区间 append [current_start, current_end] to merged current_start = start current_end = end // 步骤3：别忘记添加最后一个合并区间 append [current_start, current_end] to merged return merged ``` - Python 实现（可直接运行）： ``` def merge(intervals): if not intervals: return [] # 排序：key 为元组，确保起点相同时间按终点升序 intervals.sort(key=lambda x: (x[0], x[1])) merged = [] start, end = intervals[0] for i in range(1, len(intervals)): s, e = intervals[i] if s <= end: # 重叠 end = max(end, e) else: merged.append([start, end]) start, end = s, e merged.append([start, end]) return merged ``` - 常见变体与考点延伸： • 变体1：“插入新区间”（LeetCode 57）：先二分查找插入位置，再调用 merge 逻辑合并邻近区间，O(n) 时间。 • 变体2：“去重叠最少删除区间数”（LeetCode 435）：本质是求最大不重叠区间数 → 按 end 排序 + 贪心选最早结束的（区间调度问题）。 • 变体3：“合并后总覆盖长度”：需在合并过程中累加 (end - start)，注意避免重复计算（合并已解决）。 • 底层数据结构关联：若需频繁查询“某个点被多少个区间覆盖”，可用差分数组 + 前缀和（离散化坐标）；若需动态维护覆盖状态，可用线段树或扫描线（sweep line）算法。

赢彻科技一面

全站热榜

创作者周榜