<rt id="06g60"></rt>
Description
假設要在足夠多的會場里安排一批活動，并希望使用盡可能少的會場。設計一個有效的算法進行安排。(這個問題實際上是著名的圖著色問題。若將每一個活動作為圖的一個頂點，不相容活動間用邊相連。使相鄰頂點著有不同顏色的最小著色數，相應于要找的最小會場數。) 編程任務： 對于給定的k個待安排的活動，編程計算使用最少會場的時間表。
Input
輸入數據是由多組測試數據組成。每組測試數據輸入的第一行有1 個正整數k，表示有k個待安排的活動。接下來的k行中，每行有2個正整數，分別表示k個待安排的活動開始時間和結束時間。時間以0 點開始的分鐘計。
Output
對應每組輸入，輸出的每行是計算出的最少會場數。
Sample Input
5 1 23 12 28 25 35 27 80 36 50
Sample Output
3 #include<iostream>#include<queue>using namespace std;struct Node{ int s; int e; friend bool operator <(Node a,Node b) { return a.e > b.e; }};int main(){ int n; while(cin>>n) { int *hash = new int[n+1]; int t=0,i,maxe,index; Node p; priority_queue<Node>Q; for(i=0;i<n;i++) { scanf("%d%d",&p.s,&p.e); Q.push(p); } p = Q.top(); Q.pop(); hash[t++] = p.e; while(!Q.empty()) { p = Q.top(); Q.pop(); maxe = 0; index = 0; for(i=0 ;i<t;i++) { if(p.s >= hash[i] && maxe < hash[i]) { maxe = hash[i]; index = i; } } if(maxe == 0) hash[t++] = p.e; else hash[index] = p.e; } cout<<t<<endl; delete []hash; } return 0;}
3
#include<iostream>#include<queue>using namespace std;struct Node{ int s; int e; friend bool operator <(Node a,Node b) { return a.e > b.e; }};int main(){ int n; while(cin>>n) { int *hash = new int[n+1]; int t=0,i,maxe,index; Node p; priority_queue<Node>Q; for(i=0;i<n;i++) { scanf("%d%d",&p.s,&p.e); Q.push(p); } p = Q.top(); Q.pop(); hash[t++] = p.e; while(!Q.empty()) { p = Q.top(); Q.pop(); maxe = 0; index = 0; for(i=0 ;i<t;i++) { if(p.s >= hash[i] && maxe < hash[i]) { maxe = hash[i]; index = i; } } if(maxe == 0) hash[t++] = p.e; else hash[index] = p.e; } cout<<t<<endl; delete []hash; } return 0;}