手帐 Blog

主题

复盘 · LC 56 合并区间 ​

题目 ​

题意 ​

给一组闭区间 intervals，每个形如 [start, end]，把所有重叠或相接可合并的区间并成尽可能少的互不重叠区间，返回合并结果（顺序任意，通常按左端点排好）。

  • 「重叠」：后一段的左端点 ≤ 当前合并段的右端点，就要并进去。
  • 完全被包住的区间（如 [1,4] 包住 [2,3]）合并后仍是外面那一段。

边界：空数组；单区间；互不重叠；后段完全落在前段内；端点相接（[1,4] 与 [4,5] → [1,5]，闭区间要合并）。

涉及算法 ​

标签一句话
排序先按左端点排，重叠关系才变成「只看相邻」
线性扫描合并维护当前合并段的 end，能并就扩，不能并就落盘开新段

教程对照：按左端点 sort 在 02 · JS 刷题语法速成 练习清单里点名过本题；套路本身是「排序后扫一遍」的经典区间题。

评价我的解法 ​

思路：按左端点（再按右端点）排序 → 用 start/end 维护当前段 → 下一段起点 > end 则落盘并开新段，否则用更大的右端点扩展。这就是标准合并模板，172/172 通过。

我的代码（摘自 56-合并区间/index.js，不含测例）：

javascript
var merge = function (intervals) {
  intervals.sort((a, b) => {
    if (a[0] !== b[0]) {
      return a[0] - b[0];
    } else {
      return a[1] - b[1];
    }
  });
  if (intervals.length === 0) {
    return [];
  }
  const resArr = [];
  let start = intervals[0][0];
  let end = intervals[0][1];
  for (let i = 1; i < intervals.length; i++) {
    const item = intervals[i];
    if (item[0] > end) {
      resArr.push([start, end]);
      start = item[0];
      end = item[1];
    } else if (item[1] > end) {
      end = item[1];
    }
  }
  resArr.push([start, end]);
  return resArr;
};

对在哪：

  1. 排序键选对了：只按左端点就能保证「能合并的一定相邻」；二级按右端点不是必须，但无害。
  2. 三种关系都盖到了：断开（item[0] > end）→ 落盘；相交且更长（item[1] > end）→ 扩 end；完全被包住 → 两个 if 都不进，正确保持原 end（本地测例 [1,4],[2,3] 就是这条）。
  3. 循环后补推最后一段：漏推是这题最常见的 off-by-one，你写对了。

糙/可收的地方：

  1. 空数组判断放在 sort 之后：功能没错，习惯上先判空更干净。
  2. 二级排序可省：sort((a,b) => a[0] - b[0]) 足够；少一次比较，口述更短。
  3. 用时很长（提交备注约 10h）：终解已经是正确模板，说明卡在「想清楚再动笔」而不是复杂度档位；面试要能在几分钟内说出「先排左端点，再扫着合」。
  4. 跑分偏低：算法档位已是 O(n log n)，再抠主要是写法习惯（少分配、直接改 res 末段），不是换算法。

小结：独立写出正确合并骨架，技术上过关；要练的是口述速度和把写法收成「res 末段 + Math.max」一句式。

最佳题解 ​

排序后维护结果数组末段，能并就改右端点：

javascript
/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  if (intervals.length === 0) return [];
  intervals.sort((a, b) => a[0] - b[0]);
  const res = [[intervals[0][0], intervals[0][1]]];
  for (let i = 1; i < intervals.length; i++) {
    const last = res[res.length - 1];
    const cur = intervals[i];
    if (cur[0] > last[1]) {
      res.push([cur[0], cur[1]]);
    } else {
      last[1] = Math.max(last[1], cur[1]);
    }
  }
  return res;
};
  • 时间 O(n log n)（排序主导），空间 O(n)（结果；若不算输出则为排序开销）。
  • 为何更利落：不另开 start/end 变量；Math.max 一行覆盖「相交扩展」和「被包住不动」；空数组提前返回。

关联题目 ​

题为何相关
57. 插入区间已有序区间里插一段再合并；56 的「局部合并」版
435. 无重叠区间同样先排序，改成贪心删最少段
986. 区间列表的交集两列表双指针扫区间，合并的「求交」兄弟题
252. 会议室（若有会员）判是否重叠，排序后看相邻即可

一句话带走 ​

合并区间：先按左端点排序，再扫一遍——能接到当前右端点就 Math.max 扩，接不上就落盘开新段。