auto_ai 知识库

Appearance

区间合并是贪心算法的经典应用：给定若干区间，将所有重叠或相邻的区间合并为不重叠的区间集合。核心思路是按左端点排序后，依次扫描并维护当前合并区间的左右端点，遇到重叠则扩展，遇到分离则保存并开启新区间。

定义与核心原理 ​

问题描述 ​

给定 n 个区间 [st_i, ed_i]，合并所有重叠区间，输出最少数量的不重叠区间。

贪心策略 ​

  1. 排序：按区间左端点从小到大排序
  2. 扫描：维护当前合并区间 [st, ed]
  3. 判断：
    • 下一个区间的左端点 ≤ 当前 ed → 重叠，更新 ed = max(ed, 下一个 ed)
    • 下一个区间的左端点 > 当前 ed → 分离，保存当前区间，开启新区间

关键性质 ​

由于按左端点排序，不会出现"后续区间左端点更小但右端点更大"的情况。因此只需比较下一个区间的左端点与当前 ed，即可判断是否重叠。

操作步骤 ​

输入区间：[1,3], [2,6], [8,10], [15,18]

步骤1：按左端点排序（已有序）
步骤2：初始化当前区间 [1,3]
步骤3：扫描 [2,6]
  2 ≤ 3 → 重叠，合并为 [1, max(3,6)] = [1,6]
步骤4：扫描 [8,10]
  8 > 6 → 分离，保存 [1,6]，当前区间变为 [8,10]
步骤5：扫描 [15,18]
  15 > 10 → 分离，保存 [8,10]，当前区间变为 [15,18]
步骤6：扫描结束，保存 [15,18]

输出：[1,6], [8,10], [15,18]

代码实现 ​

cpp
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.empty()) return {};
    sort(intervals.begin(), intervals.end());  // 按左端点排序
    vector<vector<int>> res;
    int st = intervals[0][0], ed = intervals[0][1];
    for (int i = 1; i < intervals.size(); i++) {
        if (intervals[i][0] <= ed) {
            ed = max(ed, intervals[i][1]);  // 重叠，扩展右端点
        } else {
            res.push_back({st, ed});        // 分离，保存
            st = intervals[i][0];
            ed = intervals[i][1];
        }
    }
    res.push_back({st, ed});  // 保存最后一个区间
    return res;
}

复杂度分析 ​

操作时间复杂度说明
排序O(n log n)按左端点排序
扫描合并O(n)一次遍历
总时间O(n log n)排序为主
空间O(log n) 或 O(n)排序栈空间 / 结果存储

实践应用 ​

  • 区间合并模板题：LeetCode 56. 合并区间
  • 会议室安排：判断是否有足够会议室（区间重叠数）
  • 时间线合并：将多个时间段合并为连续时段
  • 扫描线算法：矩形面积并、天际线问题的基础
  • 区间调度：与"区间选点"、"不重叠区间"等问题配合

常见误区 ​

  1. 忘记排序：必须先按左端点排序，否则贪心策略不成立
  2. 只比较左端点不更新 ed：合并时 ed 应取 max(ed, 当前区间ed)，不是直接替换
  3. 边界条件：单个区间、空区间、完全包含的区间都要测试
  4. 相邻区间是否合并：题目要求"重叠或相邻"则用 &lt;=，只"重叠"则用 &lt;

一句话总结 ​

区间合并先按左端点排序再线性扫描，合并时右端点取 max(ed, 新区间ed)，总复杂度 O(n log n)；忘记排序，贪心策略就不成立。

相关概念 ​