- 正确答案：给定一个区间的集合，合并所有重叠的区间，返回不重叠的区间列表。例如输入 [[1,3],[2,6],[8,10],[15,18]]，输出 [[1,6],[8,10],[15,18]]。 - 解答思路：第一步：按每个区间的起始位置（start）升序排序，这是关键前提——只有排序后才能保证重叠只可能发生在相邻或连续区间之间，避免两两比较的O(n²)复杂度。第二步：初始化结果列表，将第一个区间作为当前待合并区间 current = intervals[0]。第三步：遍历后续每个区间 interval： - 若 interval.start <= current.end，说明重叠（注意：等于也算重叠，如 [1,4] 和 [4,6] 应合并为 [1,6]，题目中“重叠”定义为有交集，即闭区间交集非空 → 等价于 interval.start <= current.end）；此时更新 current.end = max(current.end, interval.end)。 - 否则无重叠，将 current 加入结果，并令 current = interval。第四步：循环结束后，将最后一个 current 加入结果并返回。 - 深度知识讲解： 1. 排序稳定性与比较器实现：虽然本题仅需按 start 排序，但若 start 相同，end 如何处理？实际上不影响正确性（因后续合并逻辑天然兼容），但最优实践是当 start 相同时按 end 升序排（避免冗余合并），例如 [[1,4],[1,3]] 排序后为 [[1,3],[1,4]]，合并时仍得 [[1,4]]，逻辑不变；但若误排为 [[1,4],[1,3]]，合并过程相同，无实质影响。Java 中可写 Comparator.comparingInt(a -> a[0]).thenComparingInt(a -> a[1])；Python 中 sorted(intervals, key=lambda x: (x[0], x[1]))。 2. 时间复杂度分析：排序 O(n log n)，单次扫描 O(n)，总时间复杂度 O(n log n)；空间复杂度 O(1)（不计输出空间），若原地排序（如 list.sort()）则额外空间为 O(log n)（快排递归栈深度）。 3. 边界条件深挖： - 空输入：返回空列表； - 单区间：直接返回； - 完全嵌套：[[1,10],[2,3],[4,5]] → 排序后仍是 [[1,10],[2,3],[4,5]]，合并时 [2,3] 和 [4,5] 均满足 2<=10、4<=10，故最终 current.end 不断取 max，结果为 [[1,10]]； - 相邻但不重叠：[[1,2],[3,4]] → 3 > 2，不合并，正确保留两个区间； - 相邻且需合并（题目隐含要求）：注意 LC56 明确说明“重叠”指有交集，而 [1,4] 和 [4,6] 的交集为 {4} ≠ ∅，因此必须合并。这是数学上闭区间 [a,b] ∩ [c,d] ≠ ∅ ⇔ a ≤ d 且 c ≤ b，但因已排序（a ≤ c），所以只需判断 c ≤ b 即可 —— 这正是我们用 interval[0] <= current[1] 的理论依据。 4. 数据结构选择：无需特殊数据结构，纯数组+一次遍历即可；但若扩展为“动态插入区间并实时合并”，则需平衡BST（如 Java TreeMap 存储 disjoint intervals）或线段树，支持 O(log n) 插入与合并。 5. 原地合并可行性：若要求空间复杂度严格 O(1)（不含输出），可复用输入数组前部存储结果（双指针：writeIdx 和 readIdx），但会破坏输入，面试中需主动询问是否允许修改原数组。 - 代码示例（Python，清晰版）： def merge(intervals): if not intervals: return [] # 排序：按起点升序，起点相同时按终点升序（非必需但更鲁棒） intervals.sort(key=lambda x: (x[0], x[1])) merged = [] current = intervals[0] for i in range(1, len(intervals)): interval = intervals[i] if interval[0] <= current[1]: # 重叠：闭区间有交集 current[1] = max(current[1], interval[1]) else: merged.append(current) current = interval merged.append(current) # 添加最后一个区间 return merged - 代码示例（Java，使用 ArrayList + int[][]，体现类型安全）： public int[][] merge(int[][] intervals) { if (intervals.length == 0) return new int[0][]; Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); List merged = new ArrayList<>(); int[] current = intervals[0]; for (int i = 1; i < intervals.length; i++) { int[] interval = intervals[i]; if (interval[0] <= current[1]) { current[1] = Math.max(current[1], interval[1]); } else { merged.add(current); current = interval; } } merged.add(current); return merged.toArray(new int[merged.size()][]); } - 扩展思考（高频追问方向）： Q：如何支持区间添加操作（addInterval(newInterval)）并保持合并状态？ A：维护一个已合并的 disjoint intervals 列表（升序不重叠），插入时二分查找 newInterval 应插入的位置，然后向左/右扩张合并（最多影响前后各一个区间），时间复杂度 O(n)，优化可用 TreeSet 存储 Interval 对象（自定义 compareTo 实现按 start 比较），插入+合并均摊 O(log n)。 Q：如果区间是开区间 (a,b) 或半开区间 [a,b)，合并逻辑如何变化？ A：闭区间重叠条件是 a2 ≤ b1；开区间 (a,b) 与 (c,d) 重叠 ⇔ a < d && c < b；半开 [a,b) 与 [c,d) 重叠 ⇔ a < d && c < b —— 关键是统一用“严格小于”判断间隙，此时 [1,4) 和 [4,6) 不重叠，而 [1,4] 和 [4,6] 重叠。这直接影响 if 条件中的比较符（≤ vs <）。

27实习深言科技nlp算法一面

全站热榜

创作者周榜