题目描述
优先队列解法
样例
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include<utility>
using namespace std;
int s,t,n;
int main()
{
cin>>s>>t;
cin>>n;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
for(int i=1;i<=n;i++)
{
int a,b;
cin>>a>>b;
q.push({a,b});
}
int last=s,ed=-2e9,cnt=0;
//每次选择和上一次有交集且右端点扯得最远的
while(q.size()){
auto e=q.top();
q.pop();
int l=e.first,r=e.second;
if(l<=last) ed=max(ed,r);
else {
if(l<=ed) {last=ed;ed=max(ed,r);cnt++;}
else break;
}
if(ed>=t) break;//一旦右端点大于区间右侧,就可以直接退出循环了,防止多加入边,防止出现伸出的边刚好卡在有端点,第一个可能会继续循环下去
}
if(ed>=t) cout<<cnt+1; //第一条边没有加上去
else cout<<-1;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla