【贪心】区间分组

题目

906. 区间分组 - AcWing题库

---

给定 $N$ 个闭区间 $[a_i,b_i]$ ，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。

输出最小组数。

输入格式

第一行包含整数 $N$ ，表示区间数。

接下来 $N$ 行，每行包含两个整数 $a_i,b_i$ ，表示一个区间的两个端点。

输出格式

输出一个整数，表示最小组数。

数据范围

$1 \le N \le 10^5$ ,
$-10^9 \le a_i \le b_i \le 10^9$

输入样例：

3
-1 1
2 4
3 5

输出样例：

2

解题

方法一：贪心算法

思路

贪心策略

1. 按照左端点升序排序。
2. 从前往后枚举每个区间：
   • 判断能否将该区间放入某个现有的组中（如果该区间的左端点大于某个组中所有区间的最大右端点(max_ed)则说明能放入该组中）：
     • 如果存在这样的组，则将其放进去并将该组的最大右端点(max_ed)更新为该区间的右端点。
     • 如果不存在这样的组，则开一个新组，放入该区间并更新组的最大右端点。

综上所述，我们并不需要切实地维护每一个组里的每一个区间，而只需要维护一个存有所有组的最大右端点的序列即可。
在判断某个区间是否能放入某个现存的组中时，我们发现只要该区间左端点小于等于所有组中「最大右端点最小的组」的右端点，那它一定会与所有组中的区间都存在交集（也就是说它不能放入任何一个现存组），所以应使用小根堆维护所有组的最大右端点。

证明

设题目要求的最优策略分出的组数为 $ans$，而我们的贪心策略分出的组数为 $cnt$。

1. 按照上面的贪心策略来分组，每组中的区间一定不会存在交集，所以 $cnt$ 是一个合法解，故有 $ans \le cnt$ 。
2. 因为每一次开新组的前提是「区间的左端点小于等于所有组中最大右端点最小的组的右端点」，而排序又是按照左端点升序排的，也就是说此时现存组中所有区间的左端点都一定小于等于该区间的左端点，这样以来该区间就不可避免的与现存所有组中的某个区间有交集，这时必须要开新组，否则答案不合法，因为开新组条件过于极限（不开就不合法），所以没有策略会比该策略得到的组数更少，故有 $ans \ge cnt$。

$ans = cnt$ 得证。

代码

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 10;
int n;
PII segs[N];
priority_queue<int, vector<int>, greater<int>> pq;

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d%d", &segs[i].first, &segs[i].second);
    sort(segs, segs + n, [](const auto& a, const auto& b) { return a.first < b.first; });
    pq.push(segs[0].second);
    for (int i = 1; i < n; ++i) {
        int ed = pq.top();
        if (segs[i].first > ed) pq.pop();
        pq.push(segs[i].second);
    }
    printf("%d\n", pq.size());
    
    return 0;
}