题目
给定N个闭区间[ai,bi]以及一个线段区间[s,t],请你选择尽量少的区间,将指定线段区间完全覆盖。
输出最少区间数,如果无法完全覆盖则输出-1。
题目分析
-
我们这里先做个约定,[s,t]为大区间,其他的都是小区间;
-
既然要选择尽量少的区间,则我们要尽可能使每个区间覆盖的够大
先将区间按左端点从小到大排序,先选取左端点比s小的且右端点比s大的小区间,此时,
区间[s,t]出现伪左端点:j(j是小区间的右端点),然后依次枚举满足左端点小于s的区间,
当存在小区间的右端点比大区间的伪左端点大时,更新j; -
每次选取一个最适合的的区间覆盖大区间后,更新大区间的左端点s;
-
如果存在断点则循环结束,此大区间无法覆盖;如果大区间的左端点大于或等于右端点时,区间已覆盖,循环结束;
C++代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
struct qujian{
int l,r;
}qu[N];
//结构体排序函数
bool cmp(struct qujian a,struct qujian b)
{
return a.l<b.l;
}
int main()
{
int x,y,n;
cin>>x>>y>>n;
for(int i=0;i<n;i++)
{
cin>>qu[i].l>>qu[i].r;
}
//根据左端点从小到大排序
sort(qu,qu+n,cmp);
int cnt=0;
while(x<y)
{
int j=x;
//设置flag表示是否有合法区间覆盖大区间
bool flag=false;
for(int i=0;i<n;i++)
{
//左端点比大区间的左端点小,且右端点比大区间的伪左端点大
if(qu[i].l<=x&&qu[i].r>j)
{
j=qu[i].r;
flag=true;
}
}
//每次循环结束,选取的区间数增加一个,且大区间左端点更新为伪左端点;
x=j,cnt++;
//无合法小区间覆盖大区间,即形成断点,无法覆盖
if(!flag)
{
cnt=-1;
break;
}
}
cout<<cnt<<endl;
return 0;
}