- 正确答案：给定一个区间的集合，合并所有重叠的区间。例如输入 [[1,3],[2,6],[8,10],[15,18]]，输出 [[1,6],[8,10],[15,18]]。核心解法是先按区间左端点升序排序，再线性扫描，维护一个当前合并区间 [start, end]，遇到下一个区间 [a,b] 时，若 a <= current_end，则可合并（更新 end = max(end, b)）；否则将当前区间加入结果，并重置为 [a,b]。 - 解答思路：第一步：排序——必须按 intervals[i][0]（左端点）升序排序，这是贪心策略成立的前提：只有左端点有序，才能保证后续区间不会“遗漏”左侧未处理的重叠可能。第二步：单次遍历扫描——初始化 current_start = intervals[0][0], current_end = intervals[0][1]；从 i=1 开始遍历，对每个 interval = [a,b]：若 a <= current_end → 说明重叠（注意：区间 [1,4] 和 [4,5] 是相邻但不重叠？题目定义中「重叠」包含边界相接，lc56 明确要求合并 [1,4] 和 [4,5] → 因为题目示例包含 [1,4],[4,5] → 合并为 [1,5]，故判定条件是 a <= current_end，而非 a < current_end）；此时更新 current_end = max(current_end, b)。否则（a > current_end）→ 无重叠，将 [current_start, current_end] 加入结果，重置 current_start = a, current_end = b。第三步：循环结束后，别忘了把最后一个 current 区间加入结果。 - 深度知识讲解：【底层数据结构与实现原理】本题本质是「贪心 + 排序预处理」的经典范式。其正确性依赖两个关键性质：（1）全序可比性：实数区间左端点构成全序集，排序后形成单调链，使局部最优选择（立即合并能合的）可导出全局最优（最少数量的不重叠区间）。（2）传递重叠性：若 [a,b] 与 [c,d] 重叠、[c,d] 与 [e,f] 重叠，且 c ≤ b、e ≤ d，但不能直接推出 [a,b] 与 [e,f] 重叠（反例：[1,2],[1.5,3],[2.5,4] —— [1,2] 与 [2.5,4] 不重叠）。然而，在已排序前提下（c ≥ a, e ≥ c），若 [a,b] 与 [c,d] 重叠 ⇒ c ≤ b；若 [c,d] 与 [e,f] 重叠 ⇒ e ≤ d；但 e 是否 ≤ b？不一定。所以必须用 current_end 动态扩展右界，而非仅靠前一区间判断——这正是算法中用 max(current_end, b) 更新的原因：它累积了所有已合并区间的最右边界，确保 current_end 始终是当前连通分量的上确界（supremum）。【稳定性与边界细节】 - 排序稳定性无关紧要，因区间本身无附属信息；但若输入含相同左端点的多个区间（如 [[1,3],[1,5],[2,4]]），排序后顺序不影响结果（因都按左端点排，后续扫描仍会合并）。 - 边界判定 a <= current_end 是严格依据数学定义：两闭区间 [l1,r1], [l2,r2] 重叠 ⇔ l2 <= r1 && l1 <= r2；由于已保证 l1 <= l2（排序后），故只需判 l2 <= r1 即可。【时间/空间复杂度】 - 时间：O(n log n) 主导于排序；扫描 O(n)，故总体 O(n log n)。 - 空间：O(1) 额外空间（不计输出数组）；若语言内置排序为快排（如 Python 的 Timsort 最坏 O(n)），则空间为 O(log n)（递归栈或临时数组）。【进阶变体考点】 - 若区间为开区间 (a,b) 或半开区间 [a,b)，判定条件需改为 a < current_end（开右端）或 a < current_end（左闭右开时重叠要求 l2 < r1）； - 若需返回合并后的区间数量（而非具体区间），可只维护 count 和 current_end； - 若内存受限，需原地合并（输入可修改）：在排序后，用双指针覆盖原数组，slow 指向当前合并区间位置，fast 扫描，避免额外 result 数组； - 若区间极大（如 1e9 范围），但数量少，可考虑离散化 + 差分数组 → 但本题 n 小，不必要。 - 代码示例（Python，清晰版）： def merge(intervals): if not intervals: return [] # 按左端点升序排序 intervals.sort(key=lambda x: x[0]) merged = [] current_start = intervals[0][0] current_end = intervals[0][1] for i in range(1, len(intervals)): a, b = intervals[i] if a <= current_end: # 重叠：扩展右边界 current_end = max(current_end, b) else: # 不重叠：保存当前区间，重置 merged.append([current_start, current_end]) current_start = a current_end = b # 添加最后一个区间 merged.append([current_start, current_end]) return merged - 补充：手撕时面试官可能追问的点 Q：能否不用 sort？A：可以，但需 O(n²) 暴力两两判断+合并，或用并查集（复杂度更高），无实际优势；排序是最优预处理。 Q：如果输入已按左端点排序，能否优化到 O(n)？A：可以，跳过 sort 步骤，其余不变，时间降为 O(n)。 Q：如何证明贪心选择性质？A：假设存在更优解使用了更少的区间，但我们的算法在每一步都尽可能向右扩展 current_end，因此任何其他方案的某个区间右端点必 ≤ 我们的 current_end，故区间数不可能更少（反证法）。

深言科技nlp算法日常实习一面

全站热榜

创作者周榜