有若干个活动,第i个开始时间和结束时间是[Si,fi),同一个教室安排的活动之间不能交叠,求要安排所有活动,最少需要几个教室?
Input
第一行一个正整数n (n <= 10000)代表活动的个数。
第二行到第(n + 1)行包含n个开始时间和结束时间。
开始时间严格小于结束时间,并且时间都是非负整数,小于1000000000
Output
一行包含一个整数表示最少教室的个数。
Input示例
3
1 2
3 4
2 9
Output示例
2
意思挺简单,就是求重复区间的“重复度”;也可以理解为求“线段重叠部分的“宽度”(重复次数)”
#include<bits/stdc++.h>
struct sec{
int left;
int right;
bool operator <(const sec &a)const{
return right>a.right;
}
};
int cmp(sec a,sec b){
if(a.left==b.left)
return a.right<b.right;
return a.left<b.left;
}
int main(){
int t;
cin>>t;
vector<sec> v;
sec r;
for(int i=1;i<=t;i++){
cin>>r.left>>r.right;
v.push_back(r);
}
sort(v.begin(),v.end(),cmp);
priority_queue<sec> q;
q.push(v[0]);
for(int i=1;i<t;i++){
if(v[i].left>=q.top().right){
q.pop();
q.push(v[i]);
}
else q.push(v[i]);
}
cout<<q.size()<<endl;
return 0;
}