貪心算法-會場安排問題.doc

《貪心算法-會場安排問題.doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、計算機(jī)算法設(shè)計與分析（第3版）128頁算法實現(xiàn)題4-1會場安排問題問題描述：假設(shè)要在足夠多的會場里安排一批活動，并希望使用盡可能少的會場。設(shè)計一個有效的算法進(jìn)行安排。(這個問題實際上是著名的圖著色問題。若將每一個活動作為圖的一個頂點(diǎn)，不相容活動間用邊相連。使相鄰頂點(diǎn)著有不同顏色的最小著色數(shù)，相應(yīng)于要找的最小會場數(shù)。)編程任務(wù)：對于給定的k個待安排的活動，編程計算使用最少會場的時間表。Input輸入數(shù)據(jù)是由多組測試數(shù)據(jù)組成。每組測試數(shù)據(jù)輸入的第一行有1個正整數(shù)k，表示有k個待安排的活動。接下來的k行中，每行有2

2、個正整數(shù)，分別表示k個待安排的活動開始時間和結(jié)束時間。時間以0點(diǎn)開始的分鐘計。Output對應(yīng)每組輸入，輸出的每行是計算出的最少會場數(shù)。源代碼：#includeintfnPartition(inta[],intlow,inthigh){inti,j;intx=a[low];i=low;j=high;while(i=a[i])i++;if(i

3、[i];j--;}}a[i]=x;returni;}voidfnQuickSort(inta[],intlow,inthigh){intpos;if(low-1){n=1;for(;i<=e;i++)if(a[i

4、]>=b[s])s++;elsen++;}returnn;}intmain(void){intn,i;while(1==scanf("%d",&n)){int*st=newint[n];int*et=newint[n];for(i=0;i

5、t;}return0;}輸入文件示例：輸出文件示例：531231228253527803650