贪心算法 | 扶明の小站

区间贪心

区间选点

原题链接：AcWing 905. 区间选点

描述：给定 N 个闭区间 [ $a_i,b_i$ ] [ $a_i,b_i$ ]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。

输出选择的点的最小数量。

位于区间端点上的点也算作区间内。

实现：

将每个区间按照右端点从小到大排序
从前往后依次枚举每个区间，如果当前区间已经包含了点直接continue，否则选择当前区间的右端点

证明：

证明ans<=cnt ：cnt 是一种可行方案， ans是可行方案的最优解，也就是最小值。
证明ans>=cnt ： cnt可行方案是一个区间集合，区间从小到大排序，两两之间不相交。

所以覆盖每一个区间至少需要cnt个点。

核心代码：

for(int i = 0; i < n; i++){
    int a, b;
    scanf("%d%d", &a, &b);
    r[i] = {b, a};
}
sort(r, r+n);
int ans = 1;
int p = r[0].first;
for(int i = 1; i < n; i++){
    if(p >= r[i].second) continue;
    ans++;
    p = r[i].first;
}

最大不相交区间数量

原题链接：AcWing 908. 最大不相交区间数量

描述：给定 N 个闭区间 [ $a_i,b_i$ ] [ $a_i,b_i$ ]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。

输出可选取区间的最大数量。

实现：

将每个区间按照右端点值从小到大排列
从前往后依次枚举每个区间，如果当前区间已经包含了点直接continue，否则选择当前区间的右端点

和上一个题的实现是一样的 emm

证明：每一个最大的不相交区间一定可以包含第一个结束的区间，据此推论可得每一次选择最早结束的区间即可

核心代码：参考上一题的代码

区间分组

原题链接：AcWing 906. 区间分组

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

输出最小组数。

实现：

将每个区间按照左端点值从小到大排列
从前往后处理每一个区间，判断是否能将其放到某个现有组中（当前某个区间的右端点是否小于目前待处理的区间的左端点，如不存在则新开一个组，否则及其放入区间中）

证明：对于不能加入任意现存组的的区间就已经无法加入任意组了需要新开一个组，对于任意能加入现存组的区间，由于区间已经按照左端点排序故加入任意现存组都不影响后面的分组继续加入任意组（模糊证明）

核心代码：

sort(a, a + n);

q.push(a[0].second);

for (int i = 1; i < n; i++) {
    if (q.top() < a[i].first) q.pop();
    q.push(a[i].second);
}

区间覆盖问题

原题链接：AcWing 907. 区间覆盖

描述：给定 N 个闭区间 [ $a_i,b_i$ ] [ $a_i,b_i$ ]，以及一个线段区间 [ $s,t$ ] ，请你选择尽量少的区间，将指定线段区间完全覆盖。

输出最少区间数，如果无法完全覆盖则输出 −1。

实现：

将左端点从小到大排序
从前往后一次枚举每个区间，选取能覆盖目标区间左端点去区间中选择右端点最大的区间，选完后更新目标区间

证明：每一次选取能保证覆盖且覆盖长度最长的区间能够最大化地得到最小的目标区间（模糊证明）