题意:有(N)个闭区间,选出最少的区间覆盖([1,T]),若无法覆盖,输出(-1).
题意:就是区间覆盖类贪心模板题.把每个区间按照左端点从小到大排序,每次选一个区间,使得右端点尽量大,中间一些判断细节和左右端点的衔接见代码注释.
//#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
inline int read(){
int s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
return s*w;
}
struct Cow{
int l,r;
}a[25005];
inline bool cmp(const Cow &x,const Cow &y){return x.l<y.l;}
int main(){
int n=read(),T=read();
for(int i=1;i<=n;i++){
a[i].l=read();
a[i].r=read();
}
sort(a+1,a+n+1,cmp);//按照左端点从小到大排序
int ans=0,bj=1,t=0,i=1,s;
while(t<T){
ans++;//选出的区间数+1
s=t;//t上次选完后的右端点,s当前的左端点
for(;a[i].l<=s+1&&i<=n;i++)//一定是s+1,因为是闭区间.
if(t<a[i].r)t=a[i].r;//贪心,尽量让右端点大
if(t==s&&s<T){//特判无解(区间无法衔接起来)
puts("-1");
bj=0;break;
}
}
if(bj)printf("%d
",ans);
return 0;
}