題目

有若干個活動，第i個開始時間和結束時間是[Si,fi)，同一個教室安排的活動之間不能交疊，求要安排所有活動，最少需要幾個教室？?

輸入

第一行一個正整數n (n <= 10000)代表活動的個數。
第二行到第(n + 1)行包含n個開始時間和結束時間。
開始時間嚴格小于結束時間，并且時間都是非負整數，小于1000000000

輸出

一行包含一個整數表示最少教室的個數。

輸入樣例

3
1 2
3 4
2 9

輸出樣例

2

思路：按活動的開始時間排序后，使用優先隊列，統計活動即可

源程序

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 1E9+7; const int N = 100000+5; const int dx[] = {-1,1,0,0}; const int dy[] = {0,0,-1,1}; using namespace std;struct Node{LL start;LL endd; }a[N]; bool cmp(Node a,Node b){if(a.start==b.start)return a.endd<b.endd;return a.start<b.start; } int main(){int n;scanf("%d",&n);for(int i=0;i<n;++i)scanf("%lld%lld",&a[i].start,&a[i].endd);sort(a,a+n,cmp);int res=1;priority_queue<LL,vector<LL>,greater<LL> > Q;Q.push(a[0].endd);for(int i=1;i<n;i++){if(a[i].start>=Q.top()){Q.pop();Q.push(a[i].endd);}else{res++;Q.push(a[i].endd);}}printf("%d\n",res);return 0; }

?

總結

以上是生活随笔為你收集整理的活动安排问题（51Nod-1428）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。