世界的尽头

核心思路

合并区间的关键是：先按照左端点排序，再从左到右维护当前正在合并的区间 $[st, ed]$ 。

设下一个区间为 $[l,r]$ ：

如果 $l > ed$ ，说明它与当前区间没有交集。将 $[st,ed]$ 加入答案，并从 $[l,r]$ 开始维护新区间。
如果 $l \le ed$ ，说明两个区间有交集，将当前右端点更新为 $ed = \max(ed,r)$ 。

这里默认区间是闭区间，所以 $[1,2]$ 和 $[2,3]$ 在端点 $2$ 处相交，应当合并为 $[1,3]$ 。

为什么按照左端点排序

排序后，所有区间的左端点单调不减。扫描到 $[l,r]$ 时：

如果 $l > ed$ ，后面区间的左端点只会更大，因此它们也不可能与当前区间相交，可以安全地保存当前区间。
如果 $l \le ed$ ，新区间与当前区间相交，只需要扩大右端点。左端点无需修改，因为当前区间的左端点一定不大于 $l$ 。

因此每个区间只需要扫描一次。排序的时间复杂度为 $O(n\log n)$ ，扫描的时间复杂度为 $O(n)$ ，总时间复杂度为 $O(n\log n)$ 。

AcWing 803：区间合并

题意

给定 $n$ 个闭区间，将所有有交集的区间合并，输出合并后的区间数量。

例如：

[1, 2] [2, 4] [5, 6]

前两个区间相交，合并后得到：

[1, 4] [5, 6]

答案为 $2$ 。

题解

#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
const int N = 100010;
 
int n;
 
typedef pair<int, int> PII;
 
vector<PII> segs;
 
void merge(vector<PII> &segs) {
  vector<PII> res;
 
  // pair 默认先按 first 排序，再按 second 排序
  sort(segs.begin(), segs.end());
 
  int st = -2e9, ed = -2e9;
 
  for (auto seg : segs) {
    if (seg.first > ed) {
      if (st != -2e9) {
        res.push_back({st, ed});
      }
      st = seg.first;
      ed = seg.second;
    } else {
      ed = max(ed, seg.second);
    }
  }
 
  if (st != -2e9) {
    res.push_back({st, ed});
  }
 
  segs = res;
}
 
int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    segs.push_back({l, r});
  }
 
  merge(segs);
  cout << segs.size() << endl;
 
  return 0;
}

LeetCode 56：合并区间

这道题需要返回合并后的所有区间，思路与 AcWing 803 相同。区别只是输入和输出使用 vector<vector<int>>。

当答案为空，或者新区间的左端点大于答案中最后一个区间的右端点时，直接加入新区间；否则更新最后一个区间的右端点。

class Solution {
public:
  vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
 
    vector<vector<int>> res;
 
    for (const auto& interval : intervals) {
      if (res.empty() || interval[0] > res.back()[1]) {
        res.push_back(interval);
      } else {
        res.back()[1] = max(res.back()[1], interval[1]);
      }
    }
 
    return res;
  }
};

时间复杂度为 $O(n\log n)$ ，额外空间复杂度为 $O(n)$ ，用于保存答案。

LeetCode 57：插入区间

原区间数组已经按照左端点排序，且区间之间互不重叠。插入新区间时，可以分为三个阶段：

将所有位于新区间左侧、与新区间不相交的区间加入答案。
合并所有与新区间相交的区间。
将剩余区间加入答案。

判断两个闭区间 $[a,b]$ 和 $[c,d]$ 是否相交，可以使用：

\max(a,c) \le \min(b,d)

在这道题的顺序扫描中，只要当前区间的左端点不大于新区间的右端点，就可能与新区间相交。

class Solution {
public:
  vector<vector<int>> insert(vector<vector<int>>& intervals,
                             vector<int>& newInterval) {
    vector<vector<int>> res;
    int i = 0;
    int n = intervals.size();
 
    // 完全位于新区间左侧
    while (i < n && intervals[i][1] < newInterval[0]) {
      res.push_back(intervals[i]);
      i++;
    }
 
    // 与新区间相交
    while (i < n && intervals[i][0] <= newInterval[1]) {
      newInterval[0] = min(newInterval[0], intervals[i][0]);
      newInterval[1] = max(newInterval[1], intervals[i][1]);
      i++;
    }
    res.push_back(newInterval);
 
    // 完全位于新区间右侧
    while (i < n) {
      res.push_back(intervals[i]);
      i++;
    }
 
    return res;
  }
};

因为原数组已经有序，所以不需要重新排序。时间复杂度为 $O(n)$ ，额外空间复杂度为 $O(n)$ 。

LeetCode 986：区间列表的交集

给定两个内部互不相交、且已经排序的区间列表，求它们的所有交集。

使用双指针分别指向两个列表中的区间。设当前区间为 $[a_1,a_2]$ 和 $[b_1,b_2]$ ，则交集的左右端点分别为：

l = \max(a_1,b_1), \qquad r = \min(a_2,b_2)

如果 $l \le r$ ，说明交集 $[l,r]$ 存在。之后让右端点较小的区间向后移动，因为它不可能再与另一个列表的后续区间产生新的交集。

class Solution {
public:
  vector<vector<int>> intervalIntersection(
      vector<vector<int>>& firstList,
      vector<vector<int>>& secondList) {
    vector<vector<int>> res;
    int i = 0, j = 0;
 
    while (i < firstList.size() && j < secondList.size()) {
      int l = max(firstList[i][0], secondList[j][0]);
      int r = min(firstList[i][1], secondList[j][1]);
 
      if (l <= r) {
        res.push_back({l, r});
      }
 
      if (firstList[i][1] < secondList[j][1]) {
        i++;
      } else {
        j++;
      }
    }
 
    return res;
  }
};

时间复杂度为 $O(n+m)$ ，其中 $n$ 和 $m$ 分别是两个区间列表的长度。

常见错误

忘记排序：标准区间合并必须先保证左端点单调不减。
遗漏最后一个区间：循环结束后，正在维护的 $[st,ed]$ 还没有加入答案。
混淆闭区间边界：闭区间中 l == ed 表示相交；只有 l > ed 才需要开启新区间。
直接用新区间右端点覆盖 ed：相交时应写成 ed = max(ed, r)，因为新区间可能完全包含在当前区间内。
空数组越界：使用 res.back() 前要先判断 res.empty()。

5-合并区间