贪心算法-区间问题
1. 区间选点问题概述及示例
https://www.acwing.com/problem/content/907/
上图为区间选点问题的示例。
如上图所示：黑色为数轴，蓝色为区间，红色为选择的点。若满足题目要求，最少应选两个点。
2. 区间选点问题步骤
1. 将每个区间按照右端点从小到大排序。
2. 遍历每一个区间，这里分为两种情况：
2.1 如果当前区间不含点，那么把点选在当前区间的最右侧。遍历下一个区间。
2.2 如果当前区间含点，则直接pass掉，遍历下一个区间即可。
3. 区间选点问题证明
下面对上述的步骤进行证明：
假设，res代表本题最优方案所需要的点的个数。由于根据上述算法，我们可以保证每个区间都包含1个点。因此，cnt代表使用上述算法所需要的点的个数。
1. 显然，res <= cnt。
2. 现证：res >= cnt。首先，根据上述算法，当我们需要在一个区间上选点时，该区间满足的条件为：该区间跟上一个已经包含点的区间是没有交集的。因此，当使用上述算法选了cnt个点时，就一定会保证有cnt个互不相交的区间。既然已经存在cnt个互不相交的区间的话，那么如果想要保证求得可行解，可行解一定要保证>=cnt。由于，res是众多可行解中的一个。因此，res >= cnt。得证。
3. 由于 res <= cnt && res >= cnt => res = cnt。即，本题的答案就是最优解。
证毕。
4. 区间选点问题代码
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1000010;
//定义区间
struct Range{
int l;
int r;
}range[N];
int n;
void quickSort(Range range[],int l,int r){
if(l >= r){
return;
}
int i = l-1;
int j = r+1;
Range x = range[l+r >> 1];
while(i < j){
do{i++;}while(range[i].r < x.r);
do{j--;}while(range[j].r > x.r);
if(i < j){
Range temp = range[i];
range[i] = range[j];
range[j] = temp;
}
}
quickSort(range,l,j);
quickSort(range,j+1,r);
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d",&range[i].l,&range[i].r);
}
//将区间按照右端点从小到大排序
quickSort(range,0,n-1);
//计数
int ed = -2e9;
int res = 0;
for(int i=0;i<n;i++){
//两个区间无交集
if(range[i].l > ed){
//选点
res++;
//更新指标
ed = range[i].r;
}
}
printf("%d",res);
return 0;
}
5. 最大不相交区间数量问题概述及示例
https://www.acwing.com/activity/content/problem/content/1112/
6. 最大不相交区间数量问题步骤
跟区间选点问题一模一样。这里不再赘述。
7. 最大不相交区间数量问题证明
我们假设，res为本题最优解。即，互不相交区间数量最大。而cnt代表通过上述算法选择的点的总数量。这些点可以覆盖掉所有区间。
1. 显然：res >= cnt。
2. 现证：res <= cnt。根据上述算法，我们可知：cnt代表通过上述算法选择的点的总数量。这些点可以覆盖掉所有区间。现在我们利用反证法：假设，res > cnt。代表：本题中拥有的互不相交的区间数量最大为res个。那么，我们根据上述算法，选择的点至少为res个，才可以保证覆盖掉所有区间。但是根据上述假设，只需要cnt个点就可以满足要求，矛盾。因此，res <= cnt。
3. res >= cnt && res <= cnt ，因此：res = cnt。即，利用上述算法可以得到本题的最优解。
8. 最大不相交区间数量问题代码
本代码跟区间选点问题代码一模一样。
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1000010;
//定义区间
struct Range{
int l;
int r;
}range[N];
int n;
void quickSort(Range range[],int l,int r){
if(l >= r){
return;
}
int i = l-1;
int j = r+1;
Range x = range[l+r >> 1];
while(i < j){
do{i++;}while(range[i].r < x.r);
do{j--;}while(range[j].r > x.r);
if(i < j){
Range temp = range[i];
range[i] = range[j];
range[j] = temp;
}
}
quickSort(range,l,j);
quickSort(range,j+1,r);
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d",&range[i].l,&range[i].r);
}
//将区间按照右端点从小到大排序
quickSort(range,0,n-1);
//计数
int ed = -2e9;
int res = 0;
for(int i=0;i<n;i++){
//两个区间无交集
if(range[i].l > ed){
//选点
res++;
//更新指标
ed = range[i].r;
}
}
printf("%d",res);
return 0;
}
9. 区间分组问题概述及示例
https://www.acwing.com/activity/content/problem/content/1113/
上图为该问题的示例。
10. 区间分组问题步骤
1. 将所有区间按照左端点从小到大排序。
2. 遍历每一个区间，判断当前区间是否可以放在某个现有的组中。
即，是否 l[i] > Max_r (其中,l[i]代表当前区间的左端点值，Max_r代表某个组中的所有区间右端点最大值)
2.1 如果结果为true，那么代表当前区间跟组中的每一个区间都没有交集，那么将当前区间放入现有组，并更新Max_r。
2.2 如果结果为false，那么代表当前区间跟组中的某一个区间有交集，那么开辟一个新组，将当前区间放入到新组之中。
在上述操作中，我们可以用一个小根堆来维护每一个组中右端点的最大值。在判断当前区间是否可以放入某个现有的组中时，
If 当前区间的左端点 <= 堆顶元素(最小的右端点的最大值)，代表当前区间跟每一个组中的某个区间均有交集，那么开一个新组即可。
If 当前区间的左端点 > 堆顶元素(最小的右端点的最大值)，那么将当前区间加入到右端点最大值最小的组中，更新所加入组的右端点的最大值，再将更新的值入堆即可。
11. 区间分组问题证明
接下来，我们对上述步骤进行证明：
假设，res代表最优解(最小组数)，cnt代表使用上述算法所得到的组数(一定是一个可行解，因为使用上述算法可以保证每一个组内的区间均无交集)。
1.1 显然，res <= cnt。
1.2 现证明：res >= cnt。我们分析上述算法的过程中可以发现：假设已经存在了cnt - 1个组，当前区间的左端点均小于等于这些组中右端点的最大值。那么就代表每一个组中必有一个区间跟当前区间有交集。因此，一定存在cnt - 1 个区间跟当前区间有公共点(l[i])。那么，一定存在cnt个区间只能各成一组。换句话说，只要这道题存在可行解，这个解一定大于等于cnt。而res是众多可行解中的一个解。因此,res >= cnt。
1.3 res >= cnt && res <= cnt => res = cnt。
即，采用如上算法所得到的解，就是最优解。
12. 区间分组问题代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;
struct Range{
int l;
int r;
}range[N];
int n;
void quickSort(Range range[],int l,int r){
if(l >= r){
return;
}
int i = l-1;
int j = r+1;
Range x = range[(l+r) >> 1];
while(i < j){
do{i++;}while(range[i].l < x.l);
do{j--;}while(range[j].l > x.l);
if(i < j){
swap(range[i],range[j]);
}
}
quickSort(range,l,j);
quickSort(range,j+1,r);
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
int a,b;
scanf("%d%d",&a,&b);
range[i].l = a;
range[i].r = b;
}
priority_queue<int,vector<int>,greater<int>> heap;
quickSort(range,0,n-1);
for(int i=0;i<n;i++){
//自成一组
if( heap.empty() || heap.top() >= range[i].l){
heap.push(range[i].r);
//加入现成组
}else{
heap.pop();
heap.push(range[i].r);
}
}
//堆的大小就是组的个数
printf("%d",heap.size());
return 0;
}
13. 区间覆盖问题概述及示例
https://www.acwing.com/activity/content/problem/content/1114/
上图为区间覆盖问题的示例。
14. 区间覆盖问题步骤
1. 将所有区间按照左端点从小到大排序。
2. 从前往后依次遍历每一个区间，在所有能够覆盖start的区间当中，选择一个右端点最大的区间。然后将start更新成右端点的最大值。
15. 区间覆盖问题证明
我们对上述的算法进行证明：
假设，res为最优解(最少的区间数)，cnt为使用当前算法所得到的区间数量。若问题有解，则上述算法一定可以找到cnt个区间，从而将区间覆盖。(换句话说，cnt一定是可行解)
1. res <= cnt;
2. 现证明：res >= cnt。 反证法：res < cnt。我们将res所采用的区间和cnt所采用的区间分别按照左端点排序，按照对应位置排好。从左到右选择第一个不同的区间，我们可以发现：由于start已确定，通过上述算法所选择的区间的右端点一定大于等于res所采用的区间的右端点。因此，我们可以将cnt所选择的区间替换res所选择的区间。替换之后，再寻找第一个不同的区间，再替换.....。全部替换完之后，我们可以发现：res == cnt。与res < cnt 矛盾。因此，res >= cnt。
3. res <= cnt && res >= cnt => res == cnt。
即，上述算法得到的就是最优解。
16. 区间覆盖问题代码
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100010;
struct Range{
int l;
int r;
}range[N];
void quickSort(Range range[],int l,int r){
if(l >= r){
return;
}
int i = l-1;
int j = r+1;
Range x = range[(l+r) >> 1];
while(i < j){
do{i++;}while(range[i].l < x.l);
do{j--;}while(range[j].l > x.l);
if(i < j){
swap(range[i],range[j]);
}
}
quickSort(range,l,j);
quickSort(range,j+1,r);
}
int n;
int main(){
int st,ed;
scanf("%d%d",&st,&ed);
scanf("%d",&n);
for(int i=0;i<n;i++){
int a,b;
scanf("%d%d",&a,&b);
range[i].l = a;
range[i].r = b;
}
quickSort(range,0,n-1);
int res = 0;
bool success = false;
for(int i=0;i<n;i++){
int j = i;
int r = -2e9;
while(j < n && range[j].l <= st){
r = max(r,range[j].r);
j++;
}
//无法覆盖的情况
if(r < st){
break;
}
//如果可以覆盖，将区间数量+1
res++;
//覆盖完毕的情况
if(r >= ed){
success = true;
break;
}
//更新起点
st = r;
i = j-1;
}
//如果区间无法覆盖或区间数量不够
if(!success){
res = -1;
printf("%d",res);
}else{
printf("%d",res);
}
return 0;
}
作者：gao79138
链接：https://www.acwing.com/
来源：本博客中的截图、代码模板及题目地址均来自于Acwing。其余内容均为作者原创。
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。