- 正确答案：合并区间问题的正确解法是先将所有区间按照起始位置升序排序，然后遍历排序后的区间列表，使用一个结果数组维护当前已合并的区间。对于每一个新区间，判断它是否与前一个已合并的区间重叠，如果重叠则合并（更新结束位置为两者最大值），否则将新区间加入结果数组。 - 解答思路： 1. 输入是一组区间列表，每个区间是 [start, end] 的形式。 2. 首先对这些区间按 start 升序排序。 3. 初始化一个结果列表，将第一个区间加入其中。 4. 遍历后续每一个区间： - 取出结果列表中最后一个区间（即最后一个已合并的区间）。 - 判断当前区间是否与这个最后区间重叠：即当前区间的 start <= 最后区间的 end。 - 如果重叠，则合并：更新最后区间的 end 为 max(原end, 当前end)。 - 如果不重叠，则将当前区间添加到结果列表中。 5. 返回结果列表。这个方法的时间复杂度主要由排序决定，为 O(n log n)，遍历合并过程是 O(n)，空间复杂度 O(1)（不计输出空间）。 - 深度知识讲解：本题考察的核心知识点包括： 1. **区间处理**：这是典型的区间合并类问题，常见于日程安排、资源分配、时间重叠检测等场景。关键在于理解“重叠”的定义。 - 两个区间 [a,b] 和 [c,d] 重叠的条件是：a <= d 且 c <= b。但在本题中由于我们已经按 a（即 start）排序，所以只需判断 c <= b 即可，也就是当前区间的 start <= 上一个区间的 end。 2. **贪心算法思想**：我们通过局部最优选择（每次尽可能合并）来达到全局最优。排序后，只要能合并就合并，不会漏掉更优解，因为排序保证了顺序性。 3. **排序的作用**：如果不排序，就无法通过一次遍历完成合并。排序后，我们只需要关注当前区间与前一个合并区间的右边界关系，极大简化逻辑。 4. **边界条件处理**： - 输入为空或只有一个区间时要正确返回。 - 区间是闭区间，即 [1,4] 和 [4,5] 是重叠的（端点相接也算重叠），所以判断条件是 <= 而不是 <。底层数据结构上，使用数组存储区间，每个区间是长度为2的数组或结构体。在合并过程中，我们动态维护一个“当前合并段”，这类似于滑动窗口的思想。 - 代码示例（Python 风格伪代码）： ``` def merge(intervals): if not intervals: return [] # 按照区间的起始位置排序 intervals.sort(key=lambda x: x[0]) merged = [] for interval in intervals: # 如果merged为空，或者当前区间与前一个不重叠 if not merged or merged[-1][1] < interval[0]: merged.append(interval) else: # 否则合并，更新结束位置为最大值 merged[-1][1] = max(merged[-1][1], interval[1]) return merged ``` 示例输入： intervals = [[1,3],[2,6],[8,10],[15,18]] 执行过程：排序后不变。 merged = [] 加入 [1,3] 下一个 [2,6]：2 <= 3 → 重叠，合并为 [1,6] [8,10]：8 > 6 → 不重叠，加入 → [[1,6],[8,10]] [15,18]：15 > 10 → 不重叠，加入 → [[1,6],[8,10],[15,18]] 返回 [[1,6],[8,10],[15,18]] 特殊情况测试： [[1,4],[4,5]] → 合并为 [1,5]（因为4<=4） [[1,4],[5,6]] → 不合并，两个独立区间 [[1,10],[2,3],[4,5]] → 合并为 [1,10] - 扩展知识点： 1. 类似题目：插入区间（LeetCode 57）、区间列表的交集（LeetCode 986）、会议室安排等。 2. 进阶变种：若区间是开区间，则 [1,4) 和 [4,5) 不重叠，判断条件变为 current.start < last.end 才重叠，注意边界处理。 3. 若输入区间数量极大，可考虑外部排序；若区间范围小，可用差分数组或线段树处理，但本题用排序+一次遍历是最优解。 4. 实际应用中，如日历系统中合并用户多个时间段的占用情况，或网络IP地址段合并等。 - 总结：本题是经典贪心+排序结合的问题，重点在于理解排序带来的单调性，使得一次遍历即可完成合并，避免了两两比较的 O(n^2) 复杂度。面试中需注意代码鲁棒性（空输入、单元素、边界相等）和复杂度分析。

美团面经

全站热榜

创作者周榜