- 正确答案：给定一个区间的集合，合并所有重叠的区间。例如输入 [[1,3],[2,6],[8,10],[15,18]]，输出 [[1,6],[8,10],[15,18]]。核心解法是先按区间左端点升序排序，再线性扫描，维护一个当前合并区间 [start, end]，对每个新区间 [a, b]，若 a <= current_end，则可合并（更新 current_end = max(current_end, b)）；否则将当前合并区间加入结果，并重置为 [a, b]。 - 解答思路：第一步：排序——因输入无序，必须先按 left 端点排序，确保后续扫描时区间“从左到右”出现，这是贪心策略成立的前提；第二步：单次遍历——用两个变量 start 和 end 表示当前正在构建的合并区间；第三步：判断重叠——区间 [a,b] 与 [start,end] 重叠当且仅当 a <= end（注意：闭区间，[1,4] 和 [4,6] 是重叠的，应合并为 [1,6]）；第四步：更新或提交——若重叠，end = max(end, b)；否则将 [start,end] 加入结果，重置 start=a, end=b；第五步：别忘提交最后一个区间（循环结束后需 append 当前 [start,end]）。 - 深度知识讲解：【底层数据结构】本题不依赖特殊数据结构，但考察对数组+排序+双指针式扫描的理解。关键在于理解“排序 + 贪心合并”的耦合机制：排序使问题具备最优子结构性质，而线性扫描中每一步决策（是否合并）只依赖当前状态和下一个区间，符合贪心选择性质。【时间复杂度分析】排序耗时 O(n log n)，扫描 O(n)，整体 O(n log n)；空间复杂度 O(1)（不计输出空间），若原地排序则额外空间为 O(log n)（快排递归栈深度）。【边界细节与底层原理】 • 重叠判定本质是数学不等式：两闭区间 [l1,r1], [l2,r2] 有交集 ⇔ l1 <= r2 && l2 <= r1；但本题因已排序（l2 >= l1），故只需判 l2 <= r1 即可（即 l2 <= current_end）。 • 合并后新区间右端点必为 max(r1, r2)，因为区间有序，r2 可能更大（如 [1,10] 后接 [2,5] 不扩展，但接 [3,15] 就需更新为 15）。 • 排序稳定性无关紧要，因我们只按 left 排序；但若 left 相同，按 right 降序排更优（可避免冗余更新），不过题目未要求，升序即可。【常见错误深挖】 × 忘记处理最后一个区间（最常见 bug）； × 重叠条件写成 a < end（漏掉相等情形，导致 [1,4] 和 [4,6] 不合并）； × 排序时误用 lambda x: x[1]（按右端点排），破坏贪心前提； × 在循环内直接修改输入列表（影响索引逻辑），应使用新列表收集结果。 - 代码（Python，带详细注释）： def merge(intervals): if not intervals: return [] # 步骤1：按左端点升序排序 intervals.sort(key=lambda x: x[0]) # 步骤2：初始化第一个区间为当前合并区间 start, end = intervals[0][0], intervals[0][1] result = [] # 步骤3：从第二个区间开始扫描 for i in range(1, len(intervals)): a, b = intervals[i][0], intervals[i][1] # 判断是否重叠：当前区间左端点 <= 已合并区间的右端点？ if a <= end: # 重叠：扩展右边界（取最大值） end = max(end, b) else: # 不重叠：保存当前合并区间，并重置为新区间 result.append([start, end]) start, end = a, b # 步骤4：追加最后一个合并区间 result.append([start, end]) return result - 扩展知识：【进阶变体】 • 动态插入区间：可用平衡BST（如C++ set> 或 Java TreeMap）维护不重叠区间，每次 insert 时二分查找邻近区间并合并，单次 O(log n)； • 区间覆盖计数（如“最多有几个互不重叠区间”）→ 贪心选右端点最小者； • 二维区间合并（矩形合并）→ 需扫描线算法（sweep line）+ 线段树/区间树。【工程实践注意】 • 若区间数量极大（千万级），排序可能成为瓶颈，可考虑基数排序（若坐标范围有限）； • 若内存受限，可采用外部排序 + 归并式合并（分块读入、排序、多路归并）； • 在数据库场景中，该逻辑常用于时间范围去重（如用户活跃时段合并），SQL 中可用窗口函数模拟，但性能远不如内存算法。 - 补充伪代码（强调逻辑流）：输入：intervals = [[l0,r0], [l1,r1], ..., [ln-1,rn-1]] 输出：merged = list of non-overlapping intervals if intervals is empty: return empty list sort intervals by li ascending start ← l0, end ← r0 result ← empty list for i from 1 to n-1: a ← intervals[i].left, b ← intervals[i].right if a <= end: end ← max(end, b) else: append [start, end] to result start ← a, end ← b append [start, end] to result return result

快手电商llm日常实习一面 55min

全站热榜

创作者周榜