Description
假設(shè)要在足夠多的會(huì)場(chǎng)里安排一批活動(dòng)，并希望使用盡可能少的會(huì)場(chǎng)。設(shè)計(jì)一個(gè)有效的算法進(jìn)行安排。(這個(gè)問(wèn)題實(shí)際上是著名的圖著色問(wèn)題。若將每一個(gè)活動(dòng)作為圖的一個(gè)頂點(diǎn)，不相容活動(dòng)間用邊相連。使相鄰頂點(diǎn)著有不同顏色的最小著色數(shù)，相應(yīng)于要找的最小會(huì)場(chǎng)數(shù)。) 編程任務(wù)： 對(duì)于給定的k個(gè)待安排的活動(dòng)，編程計(jì)算使用最少會(huì)場(chǎng)的時(shí)間表。
Input
輸入數(shù)據(jù)是由多組測(cè)試數(shù)據(jù)組成。每組測(cè)試數(shù)據(jù)輸入的第一行有1 個(gè)正整數(shù)k，表示有k個(gè)待安排的活動(dòng)。接下來(lái)的k行中，每行有2個(gè)正整數(shù)，分別表示k個(gè)待安排的活動(dòng)開(kāi)始時(shí)間和結(jié)束時(shí)間。時(shí)間以0 點(diǎn)開(kāi)始的分鐘計(jì)。
Output
對(duì)應(yīng)每組輸入，輸出的每行是計(jì)算出的最少會(huì)場(chǎng)數(shù)。
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;}