合并区间

合并区间问题的关键步骤是什么？

• 按区间左端点升序排序;
• 顺序扫描, 每次用结果数组的最后一个区间与当前区间比较;
• 当前区间左端点大于前一区间右端点: 两区间不重叠, 当前区间直接加入结果;
• 否则两者重叠, 把前一区间右端点更新为两者的较大值;

为什么只需比较相邻区间？

• 排序后区间按左端点递增;
• 若当前区间与结果末尾区间不重叠, 则不可能与更早的区间重叠;

合并区间如何实现？

function merge(intervals: number[][]): number[][] {
  intervals.sort((a, b) => a[0] - b[0]);
  const res: number[][] = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const current = intervals[i];
    const before = res[res.length - 1];
    if (current[0] > before[1]) res.push(current);
    else before[1] = Math.max(before[1], current[1]);
  }
  return res;
}

合并区间的复杂度是多少？

• 时间复杂度: O(n log n), 瓶颈在排序;
• 空间复杂度: O(n), 保存结果;