AcWing 907. 区间覆盖
原题链接
简单
作者:
月下邂逅
,
2024-04-24 18:51:42
,
所有人可见
,
阅读 1
C++ 代码
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int,int> pii;
vector<pii> interval;
/*
将所有区间按照左端点从小到大进行排序从前往后枚举每个区间,在所有能覆盖start的区间中,
选择右端点的最大区间,然后将start更新成右端点的最大值
*/
int main()
{
int n,l,r,s,t,end,res=0;
bool success=false;
scanf("%d%d",&s,&t);
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d%d",&l,&r);
interval.push_back({l,r});
}
sort(interval.begin(),interval.end());//左端点排序
for(int i=0;i<interval.size();i++)
{
int j=i;
end=-2e9;//因为上一轮循环只需要保存左端点信息,所以每次给右端点重新赋值以确保首个符合条件的区间的右端点信息能够保存
while(j<n&&interval[j].first<=s)//所有能覆盖左端点的区间里寻找右端点最大的
{
end=max(end,interval[j++].second);
}
s=end;//每次将当前所有覆盖区间的右端点作为左端点继续寻找
res++;
if(end>=t)
{
success=true;
break;
}
else if(end==-2e9)//区间未覆盖t且没有区间能够继续向右延申
{
break;
}
i=j-1;//每次求得的区间都是前j个区间的最优解,又因为循环会i++,所以从第j+1个区间开始计算则需要i=j-1(数组下标从0开始)
}
if(success)
{
printf("%d",res);
}
else
{
printf("-1");
}
return 0;
}