首页 > 代码库 > [贪心]活动安排问题2
[贪心]活动安排问题2
题目大意：有若干个活动，第i个开始时间和结束时间是[Si,fi)，同一个教室安排的活动之间不能交叠，求要安排所有活动，最少需要几个教室？
解题关键：策略： 按照开始时间排序优先安排活动，如果冲突，则加一个教室。
1、利用优先队列
1 #include<bits/stdc++.h> 2 #define INF 0X3F3F3F3F 3 using namespace std; 4 typedef long long ll; 5 string s; 6 pair<int,int>pp[10002]; 7 int a[26]; 8 bool flag[10002]; 9 int main(){10 priority_queue<int,vector<int>,greater<int> >q;11 int n,count=1;12 cin>>n;13 for(int i=1;i<=n;i++){14 cin>>pp[i].first>>pp[i].second;15 }16 sort(pp+1,pp+n+1);17 q.push(pp[1].second);18 for(int i=2;i<=n;i++){19 if(pp[i].first>=q.top()){20 q.pop();21 q.push(pp[i].second);22 }else{23 count++;24 q.push(pp[i].second);25 }26 }27 printf("%d\n",count);28 return 0;29 }
2、求线段相交的次数
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 vector<pair<int,int> >event; 5 int main(){ 6 int n; 7 scanf("%d",&n); 8 int st,ed; 9 for(int i=0;i<n;i++){ 10 scanf("%d%d",&st,&ed); 11 event.push_back(make_pair(st,1)); 12 event.push_back(make_pair(ed,-1)); 13 } 14 sort(event.begin(),event.end()); 15 int cnt=0,ans=0; 16 for(int i=0;i<event.size();i++){ 17 cnt+=event[i].second; 18 ans=max(ans,cnt);19 } 20 printf("%d\n",ans); 21 return 0; 22 }
[贪心]活动安排问题2
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。