跳到主要内容

AcWing 906. 区间分组

本节目标

按左端点扫描闭区间，用小根堆求互不相交的最少分组数。

这是区间排序与调度中“尽早复用资源”的母题。

查看 AcWing 原题

题意与约束​

把所有闭区间 [l,r] 分成尽可能少的组，同一组内任意两个区间不能相交。闭区间端点相等仍相交，例如 [1,2] 与 [2,3] 必须在不同组。

直接思路与瓶颈​

逐组尝试放入每个区间需要反复检查该组所有历史区间，最坏会退化为平方级。只记录组数也不够，因为能否复用取决于每组当前最后结束的位置。

贪心模型与算法推导​

按左端点升序处理区间。小根堆保存每个已用组最后一个区间的右端点，堆顶就是最早结束的组。处理 [l,r] 时，若堆顶严格小于 l，该闭区间已经完全结束，弹出它并复用此组；随后把当前 r 压入堆。堆在每次函数调用中重新建立，只表示当前这一批区间的组尾。

正确性依据​

若最早结束的组尾 end 都满足 end >= l，其他组尾更大，也都与 [l,r] 相交；当前区间不能放入任何已有组，新增组不可避免。若 end < l，把当前区间放入该组合法。选择最早结束的可复用组保留了其余更晚的组尾，不会减少未来可复用的机会；交换到任意其他可复用组也不会得到更少组数。堆大小因此始终等于已处理区间所需的最少组数。

样例执行过程​

区间 [1,3]、[2,4]、[3,5] 按左端点处理。

  1. 放入 [1,3]，堆为 [3]。
  2. 堆顶 3 >= 2，不能复用，压入 4，堆为 [3,4]。
  3. 堆顶 3 >= 3，端点相等仍相交，不能复用，压入 5。

堆大小为 3，即最少三组。

代码实现​

C++17
#include <algorithm>
#include <functional>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

int minGroups(vector<pair<int, int>> intervals) {
    sort(intervals.begin(), intervals.end());
    priority_queue<int, vector<int>, greater<int>> groupEnds;

    for (const auto& [left, right] : intervals) {
        if (!groupEnds.empty() && groupEnds.top() < left) {
            groupEnds.pop();
        }
        groupEnds.push(right);
    }
    return static_cast<int>(groupEnds.size());
}

复杂度分析​

排序和每次堆操作合计为 O(n log n)，堆最多保存 n 个组尾，空间为 O(n)。

边界与易错点​

  • 闭区间复用条件是 end < l；写成 end <= l 会错误合并端点相等的区间。
  • 空集合返回 0。
  • 每个当前右端点都要压入堆：即使刚复用某个组，它的新组尾也已改变。

模式迁移​

“最少会议室”“最少机器数”等问题若端点语义相同，都可把会议结束时间作为组尾放入小根堆。先确认端点是否允许无缝衔接，再确定严格或非严格的复用条件。