Week3 C-区间覆盖

2023-12-15 03:48

文章标签 覆盖区间 week3

本文主要是介绍Week3 C-区间覆盖，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述：

数轴上有 n (1<=n<=25000)个闭区间 [ai, bi]，选择尽量少的区间覆盖一条指定线段 [1, t]（ 1<=t<=1,000,000）。
覆盖整点，即(1,2)+(3,4)可以覆盖(1,4)。
不可能办到输出-1

输入输出：

Input：第一行：N和T
第二行至N+1行: 每一行一个闭区间。

output：选择的区间的数目，不可能办到输出-1

解题思路：

区间覆盖的贪心算法是：因为要选取最少的区间去覆盖整个现端，故应该选择包含该起点且右端点最大的区间。首先对所有区间进行排序，按照左端点升序，右端点降序的方式。从第一个区间开始遍历，若区间包含起点，且右端点r最大，则选取该区间，下一次的起点是r+1，按照贪心选取一直遍历下去，直到覆盖该线段。从每个起点开始后的第一个区间，如果左端点比r+1要大，之后的区间的左端点只会更大，这个时候及时停止算法，无法覆盖该区间（也是一种可行性剪枝）。

实验代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
struct qujian
{int l;int r;	bool operator<(const qujian& q) const{if(l!=q.l)return l<q.l; 			//左端点升序 else return r>q.r; 			//右端点降序 }
};
int fugai(int t,int n,qujian* q)
{int start=1;sort(q,q+n);		//先排序 int k=0,tot=0; 			//k记录待考察区间，tot记录覆盖区间数 while(start<=t){int best=k;						//从第k个区间开始 if(q[k].l>start)return -1; int i; for(i=k+1;i<n;i++)			//选择起点在start的最长的区间 {if(q[i].l>start)			//不一定有恰好等于的，只考察左端点不在start后的 {break;}	if(q[i].r>=q[best].r)		 best=i;}k=i;					//下个循环从i开始 tot++;					//覆盖区间数加一start=q[best].r+1;		//覆盖起点改变 ,访问会越界 if(i==n)				//第二个退出while循环的条件，如果到了最后一个区间,说明比较完毕 {//要判断是否覆盖完 if(start>t)return tot; elsereturn -1;				//说明无法覆盖 }} return tot;
} int main(void)
{int N,T;scanf("%d%d",&N,&T);qujian q[25000];for(int i=0;i<N;i++){scanf("%d%d",&q[i].l,&q[i].r);}printf("%d\n",fugai(T,N,q));return 0;
}