[贪心]活动安排问题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
",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
",ans);  
21     return 0;  
22 }