AcWing 907. 区间覆盖
原题链接
简单
作者:
qing123
,
2022-05-01 22:48:19
,
所有人可见
,
阅读 154
#include<iostream>
#include<cstring>
#include<algorithm>
const int N = 1e5+10;
using namespace std;
struct Range
{
int l,r;
bool operator < (const Range& w)const
{
return l<w.l;
}
}range[N];
int main()
{
int st,ed;
int n;
cin>>st>>ed;
cin>>n;
for(int i=0;i<n;i++)
{
int l,r;
scanf("%d%d",&l,&r);
range[i]={l,r};
}
sort(range,range+n);
/*
贪心选择:能覆盖左边界的,有边界最大的边
双指针算法不断更新区间
*/
int res=0;//记录个数
bool flag=false;
for(int i=0;i<n;i++)//n个区间中选
{
int j=i,r=-2e9;//从i开始进行找
while(j<n&&range[j].l<=st)//满足调剂的区间
{
r=max(r,range[j].r);
j++;
}
if(st>r)//无解
{
res=-1;
break;
}
res++;//个数加1
if(r>=ed)
{
flag=true;
break;
}
i=j-1;
st=r;
}
if(!flag)res=-1;
cout<<res<<endl;
return 0;
}