题意:
给定N个时间区间和时间T,求最少需要多少个区间覆盖总区间[1,T],无法覆盖区域[1,T]时输出-1。
例如T=10,有3个区间[1,7],[3,6],[8,10],则最少需要两个区间来覆盖,选择区间1和区间3。
思路:
思路很简单,主要是细节问题。简单说一说吧,首先是将时间区间就行排序,这是贪心问题很常见的操作,开始时间从小到大,开始时间相等则结束时间从大到小,接下来就要选择区间,我们肯定选择排序后的第一个区间,如果这个区间的开始时间大于1,肯定是不可能全部覆盖的,输出-1,接下来选择开始时间与已经选择的最后一个区间的结束时间匹配的,并且结束时间最大,其中要注意细节问题,有可能区间不连接,要进行判断,不然是死循环,还有就是选择完了,最后的结束时间还要大于等于T,题目数据有可能不满足这个情况,要进行判断。
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=30000;
struct Point{
int start,end;bool operator <(const Point &a)const{
if(a.start==start)return a.end<end;elsereturn a.start>start; }
}p[maxn];
int main()
{
int n,T;scanf("%d%d",&n,&T);for(int i=0;i<n;i++){
scanf("%d%d",&p[i].start,&p[i].end);if(p[i].start>p[i].end)swap(p[i].start,p[i].end);}sort(p,p+n);bool isok=true;int start=p[0].start,end=p[0].end,cnt=1,node=0,node_now=0;if(start>1){
printf("-1\n");return 0;}for(int i=1;i<n&&isok;){
int end_t=end;while(i<n&&p[i].start-end<=1){
if(p[i].end>end_t){
end_t=p[i].end;node=i;}i++;}if(node!=node_now)cnt++,node_now=node;start=p[node].start;end=p[node].end;if(end>=T||i>=n)break;if(p[i].start-end>1)isok=false;}if(isok&&end>=T)printf("%d\n",cnt);elseprintf("-1\n");return 0;
}