- 正确答案：给定一个区间的集合，合并所有重叠的区间，返回不重叠的区间列表。核心步骤是：先按区间左端点升序排序；然后遍历排序后的区间，维护一个当前合并区间 [start, end]，若下一个区间与当前区间重叠（即 next.start <= current.end），则扩展当前区间的右端点为 max(current.end, next.end)；否则将当前区间加入结果，并重置为下一个区间。 - 解答思路： 1. 边界处理：若输入为空或只有一个区间，直接返回原数组。 2. 排序：按每个区间的 start 升序排序（若 start 相同，可按 end 升序，但非必须）。这是关键预处理——只有排序后才能线性扫描合并，避免两两比较的 O(n²) 复杂度。 3. 线性扫描合并：初始化 current = intervals[0]，从 i=1 开始遍历： - 若 intervals[i][0] <= current[1]，说明重叠（注意：闭区间 [a,b] 和 [c,d] 重叠当且仅当 c <= b，因为 [1,4] 和 [4,5] 视为可合并，题干明确“重叠或相邻”均需合并）； - 则更新 current[1] = max(current[1], intervals[i][1])； - 否则将 current 加入结果，令 current = intervals[i]。 4. 循环结束后，将最后一个 current 加入结果。时间复杂度 O(n log n)，主要消耗在排序；空间复杂度 O(1)（不计输出空间）。 - 深度知识讲解：【底层数据结构视角】本题本质是“有序区间集的动态维护”。排序是将无序集合转化为具有单调性的序列，从而将二维重叠判断降维为一维顺序扫描。这体现了“预处理 + 贪心扫描”的经典范式。【重叠判定的数学本质】两个闭区间 [a,b] 和 [c,d] 有交集 ⇔ max(a,c) <= min(b,d)；但合并时只需判断是否能连通：即 c <= b（因为已保证 a <= c，排序后），此时并集为 [a, max(b,d)]。该判定比求交集更轻量，是贪心正确性的基础。【稳定性与原地性】排序算法选择影响稳定性：若使用稳定排序（如归并排序），相同 start 的区间相对顺序不变，但本题无需此性质；实际面试中 std::sort（快排/堆排混合）即可，因只关心合并结果，不关心原始顺序。【边界鲁棒性】需特别注意整数溢出场景（虽本题约束为 10⁴ 内，但工业级实现应考虑 long 或使用安全比较）；另外，空输入、单元素、全重叠（如 [[1,2],[2,3],[3,4]]）、全不重叠（如 [[1,2],[3,4]]）均为典型测试用例，必须覆盖。【进阶延伸】若区间动态插入（流式输入），可用 Interval Tree（红黑树实现）或 SortedList + 二分查找，支持 O(log n) 插入与 O(k + log n) 合并（k 为被合并区间数）；此时核心是 findPredecessor（找左边界 ≤ new.start 的最大区间）和 findSuccessor（找右边界 ≥ new.end 的最小区间）。 - 代码示例（C++，标准库风格，含注释）： vector> merge(vector>& intervals) { if (intervals.empty()) return {}; // 排序：按左端点升序，左端点相同时按右端点升序（非必需，但增强可读性） sort(intervals.begin(), intervals.end(), [](const vector& a, const vector& b) { return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]); }); vector> result; vector current = intervals[0]; for (int i = 1; i < intervals.size(); ++i) { // 重叠判定：当前区间右端点 >= 下一个区间左端点 if (current[1] >= intervals[i][0]) { // 合并：扩展右端点为两者最大值（处理嵌套情况，如 [1,5] 和 [2,3]） current[1] = max(current[1], intervals[i][1]); } else { // 不重叠：保存当前区间，重置为新区间 result.push_back(current); current = intervals[i]; } } // 尾部剩余区间 result.push_back(current); return result; } - 补充说明（面试高频追问点）： Q：能否原地合并（不额外申请 result vector）？ A：可以，但需在原数组上 swap 或标记无效区间，最后 resize。但会破坏输入，且代码可读性下降，一般不推荐；除非题目明确要求空间 O(1)（此时需说明 trade-off）。 Q：如果区间是开区间 (a,b) 或半开区间 [a,b)，重叠判定如何变？ A：开区间 (a,b) 与 (c,d) 重叠 ⇔ a < d && c < b；半开 [a,b) 与 [c,d) 重叠 ⇔ a < d && c < b。核心是把 <= 改为 <，因端点不包含。 Q：如何验证合并结果的正确性？ A：数学归纳法：① 排序后第一个区间必为结果首区间左端点最小者；② 归纳假设前 k 个合并正确，则第 k+1 步的贪心选择（只要能合并就合并）不会导致后续无法合并更优解——因为排序保证了所有可能与 current 重叠的区间都连续出现在其后，延迟合并不会获得更少区间数（反证：若跳过某个可合并区间导致最终区间数增加，则该区间本应被吸收，矛盾）。

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

全站热榜

创作者周榜