貪心算法論文.doc

山東省農(nóng)業(yè)管理干部學院畢業(yè)論文題 目： 貪心算法應用研究 姓 名 ： 盛國選 畢業(yè)學院 ： 山東省農(nóng)業(yè)管理干部學院 專業(yè)班級 ： 08級計算機系軟件1班 學 號 ： 2008052001208 指導教師 ： 張艷君 日 期 ： 年 月 日 XIV目 錄1. 貪心算法的基本知識概述21.1 貪心算法定義21.2 貪心算法的基本思路及實現(xiàn)過程21.3貪心算法的核心21.4貪心算法的基本要素21.5 貪心算法的理論基礎41.6 貪心算法存在的問題52.貪心算法經(jīng)典應用舉例52.1刪數(shù)問題52.2 汽車加油問題72.3會場安排問題93.總結(jié)13參考文獻13摘 要在求最優(yōu)解問題的過程中，依據(jù)某種貪心標準，從問題的初始狀態(tài)出發(fā)，直接去求每一步的最優(yōu)解，通過若干次的貪心選擇，最終得出整個問題的最優(yōu)解，這種求解方法就是貪心算法。從貪心算法的定義可以看出，貪心法并不是從整體上考慮問題，它所做出的選擇只是在某種意義上的局部最優(yōu)解，而由問題自身的特性決定了該題運用貪心算法可以得到最優(yōu)解。貪心算法所作的選擇可以依賴于以往所作過的選擇，但決不依賴于將來的選擇，也不依賴于子問題的解，因此貪心算法與其它算法相比具有一定的速度優(yōu)勢。如果一個問題可以同時用幾種方法解決，貪心算法應該是最好的選擇之一。本文講述了貪心算法的含義、基本思路及實現(xiàn)過程，貪心算法的核心、基本性質(zhì)、特點及其存在的問題。并通過貪心算法的特點舉例列出了以往研究過的幾個經(jīng)典問題，對于實際應用中的問題，也希望通過貪心算法的特點來解決。關(guān)鍵詞：貪心算法；最小生成樹；多處最優(yōu)服務次序問題；刪數(shù)問題緒 論 為了滿足人們對大數(shù)據(jù)量信息處理的渴望，為解決各種實際問題，計算機算法學得到了飛速的發(fā)展，線性規(guī)劃、動態(tài)規(guī)劃、貪心策略等一系列運籌學模型紛紛運用到計算機算法學中，產(chǎn)生了解決各種現(xiàn)實問題的有效算法。雖然設計一個好的求解算法更像是一門藝術(shù)而不像是技術(shù) ,但仍然存在一些行之有效的、能夠用于解決許多問題的算法設計方法 ,你可以使用這些方法來設計算法 ,并觀察這些算法是如何工作的。一般情況下,為了獲得較好的性能,必須對算法進行細致的調(diào)整。但是在某些情況下,算法經(jīng)過調(diào)整之后性能仍無法達到要求,這時就必須尋求另外的方法來求解該問題。當一個問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)和貪心選擇性質(zhì)時，貪心算法通常會給出一個簡單、直觀和高效的解法。貪心算法通過一系列的選擇來得到一個問題的解。它所作的每一個選擇都是在當前狀態(tài)下具有某種意義的最好選擇，即貪心選擇；并且每次貪心選擇都能將問題化簡為一個更小的與原問題具有相同形式的子問題。盡管貪心算法對許多問題不能總是產(chǎn)生整體最優(yōu)解，但對諸如最短路徑問題、最小生成樹問題，以及哈夫曼編碼問題等具有最優(yōu)子結(jié)構(gòu)和貪心選擇性質(zhì)的問題卻可以獲得整體最優(yōu)解。而且所給出的算法一般比動態(tài)規(guī)劃算法更加簡單、直觀和高效。1. 貪心算法的基本知識概述1.1 貪心算法定義貪心算法可以簡單描述為：對一組數(shù)據(jù)進行排序，找出最小值，進行處理，再找出最小值，再處理。也就是說貪心算法是一種在每一步選擇中都采取在當前狀態(tài)下最好或最優(yōu)的選擇，從而希望得到結(jié)果是最好或最優(yōu)的算法。貪心算法是一種能夠得到某種度量意義下的最優(yōu)解的分級處理方法，通過一系列的選擇來得到一個問題的解，而它所做的每一次選擇都是當前狀態(tài)下某種意義的最好選擇，即貪心選擇。即希望通過問題的局部最優(yōu)解來求出整個問題的最優(yōu)解。這種策略是一種很簡潔的方法，對許多問題它能產(chǎn)生整體最優(yōu)解，但不能保證總是有效，因為它不是對所有問題都能得到整體最優(yōu)解，只能說其解必然是最優(yōu)解的很好近似值。1.2 貪心算法的基本思路及實現(xiàn)過程1 貪心的基本思想用局部解構(gòu)造全局解，即從問題的某一個初始解逐步逼近給定的目標，以盡可能快地求得更好的解。當某個算法中的某一步不能再繼續(xù)前進時，算法停止。貪心算法思想的本質(zhì)就是分治，或者說：分治是貪心的基礎。每次都形成局部最優(yōu)解，換一種方法說，就是每次都處理出一個最好的方案。利用貪心策略解題，需要解決兩個問題：（1）該題是否適合于用貪心策略求解；（2）如何選擇貪心標準，以得到問題的最優(yōu)/較優(yōu)解。2貪心算法的實現(xiàn)過程（1）應用同一規(guī)則F，將原問題變?yōu)橐粋€相似的、但規(guī)模更小的子問題；（2）從問題的某一初始解出發(fā)：While（能朝給定目標前進一步） 求出可行解的一個解元素；（3）由所有解元素組合成問題的一個可行解。1.3貪心算法的核心貪心算法的核心問題是選擇能產(chǎn)生問題最優(yōu)解的最優(yōu)度量標準，即具體的貪心策略。貪心策略是指從問題的初始狀態(tài)出發(fā)，通過若干次的貪心選擇而得出最優(yōu)值(或較優(yōu)解)的一種解題方法。其實，從“貪心策略”一詞我們便可以看出，貪心策略總是做出在當前看來是最優(yōu)的選擇，也就是說貪心策略并不是從整體上加以考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)解，而許多問題自身的特性決定了該題運用貪心策略可以得到最優(yōu)解或較優(yōu)解。1.4貪心算法的基本要素1貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。在動態(tài)規(guī)劃算法中，每步所做的選擇往往依賴于相關(guān)子問題的解。因而只有在解出相關(guān)子問題后，才能做出選擇。而在貪心算法中，僅在當前狀態(tài)下做出最好選擇，即局部最優(yōu)選擇。然后再去解做出這個選擇后產(chǎn)生的相應的子問題。貪心算法所做的貪心選擇可以依賴于以往所做過的選擇，但決不依賴于將來所做的選擇，也不依賴于子問題的解。正是由于這種差別，動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所做的貪心選擇最終導致問題的整體最優(yōu)解。首先考察問題的一個整體最優(yōu)解，并證明可修改這個最優(yōu)解，使其以貪心選擇開始。做了貪心選擇后，原問題簡化為規(guī)模更小的類似子問題。然后，用數(shù)學歸納法證明，通過每一步做貪心選擇，最終可得到問題的整體最優(yōu)解。其中，證明貪心選擇后的問題簡化為規(guī)模更小的類似子問題的關(guān)鍵在于利用該問題的最優(yōu)子結(jié)構(gòu)性質(zhì)。2最優(yōu)子結(jié)構(gòu)性質(zhì)當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。運用貪心策略在每一次轉(zhuǎn)化時都取得了最優(yōu)解。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用貪心算法或動態(tài)規(guī)劃算法求解的關(guān)鍵特征。貪心算法的每一次操作都對結(jié)果產(chǎn)生直接影響，而動態(tài)規(guī)劃則不是。貪心算法對每個子問題的解決方案都做出選擇，不能回退；動態(tài)規(guī)劃則會根據(jù)以前的選擇結(jié)果對當前進行選擇，有回退功能。動態(tài)規(guī)劃主要運用于二維或三維問題，而貪心一般是一維問題。3貪心算法的特點貪心算法的最大特點就是快，通常是線性二次式，不需要多少額外的內(nèi)存。一般二次方級的存儲要浪費額外的空間，而且那些空間經(jīng)常得不出正解。但是，使用貪心算法時，這些空間可以幫助算法更容易實現(xiàn)且更快執(zhí)行。如果有正確貪心性質(zhì)存在，那么一定要采用。因為它容易編寫，容易調(diào)試，速度極快，并且節(jié)約空間。幾乎可以說，此時它是所有算法中最好的。但是應該注意，貪心算法有兩大難點：（1）如何貪心怎樣用一個小規(guī)模的解構(gòu)造更大規(guī)模的解呢?總體上，這與問題本身有關(guān)。但是大部分都是有規(guī)律的。正因為貪心有如此性質(zhì)，它才能比其他算法快。具有應當采用貪心算法的問題，當“貪心序列”中的每項互異且當問題沒有重疊性時，看起來總能通過貪心算法取得（近似）最優(yōu)解的。或者，總有一種直覺在引導我們對一些問題采用貪心算法。其中“找零錢”這個問題就是一個例子。題中給出的硬幣面值事實上具有特殊性，如果面值發(fā)生變化，可能貪心算法就不能返回最優(yōu)解了。但是，值得指出的是，當一個問題具有多個最優(yōu)解時，貪心算法并不能求出所有最優(yōu)解。另外，我們經(jīng)過實踐發(fā)現(xiàn)，單純的貪心算法是順序處理問題的；而且每個結(jié)果是可以在處理完一個數(shù)據(jù)后即時輸出的。（2）貪心的正確性要證明貪心性質(zhì)的正確性，才是貪心算法的真正挑戰(zhàn)，因為并不是每次局部最優(yōu)解都會與整體最優(yōu)解之間有聯(lián)系，往往靠貪心算法生成的解不是最優(yōu)解。這樣，貪心性質(zhì)的證明就成了貪心算法正確的關(guān)鍵。對某些問題貪心性質(zhì)也許是錯的，即使它在大部分數(shù)據(jù)中都是可行的，但還必須考慮到所有可能出現(xiàn)的特殊情況，并證明該貪心性質(zhì)在這些特殊情況中仍然正確。而這樣容易陷入證明不正確貪心性質(zhì)的泥塘中無法自拔，因為貪心算法的適用范圍并不大，而且有一部分極難證明，若是沒有把握，最好不要冒險，還有其他算法會比它要保險。1.5 貪心算法的理論基礎正如前文所說的那樣，貪心策略是最接近人類認知思維的一種解題策略。但是，越是顯而易見的方法往往越難以證明。下面我們就來介紹貪心策略的理論擬陣。“擬陣”理論是一種能夠確定貪心策略何時能夠產(chǎn)生最優(yōu)解的理論，雖然這套理論還很不完善，但在求解最優(yōu)化問題時發(fā)揮著越來越重要的作用。擬陣M定義為滿足下面3個條件的有序?qū)Γ⊿，I）：（1）S是非空有限集；（2）I是S的一類具有遺傳性質(zhì)的獨立子集族，即若BI，則B是S的獨立子集，且B的任意子集也都是S的獨立子集?？占貫镮的成員；（3）I滿足交換性質(zhì)，即若AI，BI且|A|B|，則存在某一元素xB-A，使得AxI。定理2.1 擬陣M中所有極大獨立子集具有相同大小。引理2.1 （擬陣的貪心選擇性質(zhì)）設M=（S，I）是具有權(quán)函數(shù)M的帶權(quán)擬陣，且S中元素依權(quán)值從大到小排列，又設xS是S中第一個使得x是獨立子集元素，則存在S的最優(yōu)子集A使得xA。引理2.2 設M=(S，I)是擬陣。若S中元素x不是空集的一個可擴元素，則x也不可能是S中任一獨立子集A的可擴展元素。引理2.3 （擬陣的最優(yōu)子結(jié)構(gòu)性質(zhì)）設x是求帶權(quán)擬陣M=（S，I）的最優(yōu)子集的貪心算法Greedy所選擇的S中的第一個元素。那么，原問題可簡化為求帶權(quán)擬陣M=（S，I）的最優(yōu)子集問題，其中S=y|yS且x，yII=B|BS-x且BxIM的權(quán)函數(shù)是M的權(quán)函數(shù)在S上的限制（稱M為M關(guān)于元素x的收縮）。定理2.4（帶權(quán)擬陣貪心算法的正確性）高M=（S，I）是具有權(quán)函數(shù)W的帶權(quán)擬陣，算法Greedy返回M的最優(yōu)子集。適宜于用貪心策略來求解的許多問題都可以歸結(jié)為在加權(quán)擬陣中找一個具有最大權(quán)值的獨立子集的問題，即給定一個加權(quán)擬陣M=（S，I），若能找出一個獨立且具有最大可能權(quán)值的子集A，且A不被M中比它更大的獨立子集所包含，那么A為最優(yōu)子集，也是一個最大的獨立子集。我們認為，針對絕大多數(shù)的信息學問題，只要它具備了“擬陣”的結(jié)構(gòu)，便可用貪心策略求解。擬陣理論對于我們判斷貪心策略是否適用于某一復雜問題是十分有效的。1.6 貪心算法存在的問題（1）不能保證求得的最后解是最佳的。由于貪心策略總是采用從局部看來是最優(yōu)的選擇，因此并不從整體上加以考慮；（2）貪心算法只能用來求某些最大或最小解的問題；（3）貪心算法只能確定某些問題的可行性范圍。2.貪心算法經(jīng)典應用舉例2.1刪數(shù)問題問題的提出問題提出：給定n位正整數(shù)a，去掉其中任意k=n個數(shù)字后，剩下的數(shù)字按原次序排列組成一個新的正整數(shù)。對于給定的n位正整數(shù)a和正整數(shù)k，設計一個算法找出剩下數(shù)字組成的新數(shù)最小的刪數(shù)方案。貪心算法策略分析：n位數(shù)a可表示為x1x2xixjxkxn，要刪去k位數(shù)，使得剩下的數(shù)字組成的整數(shù)最小。設本問題為T，其最優(yōu)解A=(y1，y2yk)表示依次刪去的k個數(shù)，在刪去k個數(shù)后剩下的數(shù)字按原次序排成的新數(shù)。即最優(yōu)值記為TA。 本問題采用貪心算法求解，采用最近下降點優(yōu)先的貪心策略：即x1x2xixj；如果xkxj，則刪去xj，即得到一個新的數(shù)且這個數(shù)為n一1位中為最小的數(shù)Nl，可表示為x1x2xixkxmxn。對N1而言，即刪去了1位數(shù)后，原問題T變成了需對n-1位數(shù)刪去k-1個數(shù)新問題T。新問題和原問題相同，只是問題規(guī)模由n減小為n-1，刪去的數(shù)字個數(shù)由k減少為k-1。基于此種刪除策略，對新問題T，選擇最近下降點的數(shù)進行刪除，如此進行下去，直至刪去k個數(shù)為止。問題的貪心選擇性質(zhì) 先來證明該問題具有貪心選擇性質(zhì)，即對問題T刪除最近下降點的數(shù)xj后得到的N1是n一1位數(shù)是中最小的數(shù)。 根據(jù)數(shù)的進制特點，對a按權(quán)展開得： a=x1*10n-1+x2*10n-2+xi*10n-i+xj*10n-j+xk*10n-k+xn 則有：Nl=x1*10n-2+x2*10n-3+xi*10n-i-1+xk*10n-k+xn假設刪去的不是xj而是其它位，則有N2=x1*10n-2+x2*10n-3+xi*10n-i-1+xj*10n-k+xn因為有x1x2xixk，則有NlN2。 因此刪數(shù)問題滿足貪心選擇性質(zhì)。 刪數(shù)問題的C+代碼：#include #include using namespace std; int main() string n; int s,i,x,l,m; printf(請輸入一個正整數(shù)和將要刪去的個數(shù)!n); while(cinns) i=-1,m=0,x=0; l=n.length(); while(xni+1)/出現(xiàn)遞減,刪除遞減的首數(shù)字 n=n.erase(i,1); x+;/ x統(tǒng)計刪除數(shù)字的個數(shù) i=-1;/從頭開始查遞減區(qū)間 if(i=l-x-2&xs) m=1;/已經(jīng)無遞減區(qū)間,m=1脫離循環(huán) printf(最后結(jié)果為:n); coutn.substr(0,l-s+x);/只打印剩下的左邊l-(s-x)個數(shù)字 問題的最優(yōu)子結(jié)構(gòu)性質(zhì)在進行了貪心選擇后，原問題T就變成了對N1如何刪去k-1個數(shù)的問題T，是原問題的子問題。若A=(xj，A)是原問題T的最優(yōu)解，則A是子問題T的最優(yōu)解，其最優(yōu)值為TA。 證明：假設A不是子問題T的最優(yōu)解，其子問題的最優(yōu)解為B，其最優(yōu)值記為TB，則有TBTA。而根據(jù)TA的定義可知：TA= TA+xj*1On-j，而TBTA，因此有TB+xj*1On-jN，則不可能到達終點；C 加油站間的距離相等，即i=aj=LN，則加油次數(shù)k=n/N(n%N=0)或k=n/N+1(n%N！=0)；D 加油站間的距離不相等，即i！=aj，則加油次數(shù)k通過貪心算法求解。貪心算法策略該題目求加油最少次數(shù)，即求最優(yōu)解的問題，可分成幾個步驟，一般來說，每個步驟的最優(yōu)解不一定是整個問題的最優(yōu)解，然而對于有些問題，局部貪心可以得到全局的最優(yōu)解。貪心算法將問題的求解過程看作是一系列選擇，從問題的某一個初始解出發(fā)，向給定目標推進。推進的每一階段不是依據(jù)某一個固定的遞推式，而是在每一個階段都看上去是一個最優(yōu)的決策（在一定的標準下）。不斷地將問題實例歸納為更小的相似的子問題，并期望做出的局部最優(yōu)的選擇產(chǎn)生一個全局得最優(yōu)解。由于汽車是由始向終點方向開的，我們最大的麻煩就是不知道在哪個加油站加油可以使我們既可以到達終點又可以使我們加油次數(shù)最少。提出問題是解決的開始。為了著手解決遇到的困難，取得最優(yōu)方案。我們可以假設不到萬不得已我們不加油，即除非我們油箱里的油不足以開到下一個加油站，我們才加一次油。在局部找到一個最優(yōu)的解。每加一次油我們可以看作是一個新的起點，用相同的遞歸方法進行下去。最終將各個階段的最優(yōu)解合并為原問題的解得到我們原問題的求解。貪心算法正確性證明(1)貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。對于一個具體的問題，要確定它是否具有貪心性質(zhì)，我們必須證明每一步所作的貪心選擇最終導致問題的一個整體最優(yōu)解。該題設在加滿油后可行駛的N千米這段路程上任取兩個加油站、，且距離始點比距離始點近，則若在加油不能到達終點那么在加油一定不能到達終點，因為m+Nn+N，即在B點加油可行駛的路程比在A點加油可行駛的路程要長n-m千米，所以只要終點不在B、C之間且在C的右邊的話，根據(jù)貪心選擇，為使加油次數(shù)最少就會選擇距離加滿油得點遠一些的加油站去加油，因此，加油次數(shù)最少滿足貪心選擇性質(zhì)。(2)最優(yōu)子結(jié)構(gòu)性質(zhì)：當一個問題大的最優(yōu)解包含著它的子問題的最優(yōu)解時，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。由于（b1，b2，bn）是這段路程加油次數(shù)最少的一個滿足貪心選擇性質(zhì)的最優(yōu)解，則易知若在第一個加油站加油時，b1=1，則（b2，b3，bn）是從a2到an這段路程上加油次數(shù)最少且這段路程上的加油站個數(shù)為（a2，a3，an）的最優(yōu)解，即每次汽車中剩下的油不能在行駛到下一個加油站時我們才在這個加油站加一次油，每個過程從加油開始行駛到再次加油滿足貪心且每一次加油后相當于與起點具有相同的條件，每個過程都是相同且獨立，也就是說加油次數(shù)最少具有最優(yōu)子結(jié)構(gòu)性質(zhì)。貪心算法時間復雜度分析由于若想知道該在哪個加油站加油就必須遍歷所有的加油站，且不需要重復遍歷，所以時間復雜度為O(n)。2.3會場安排問題問題的提出假設要在足夠多的會場里安排一批活動，并希望使用盡可能少的會場。設計一個有效的貪心算法進行安排。(這個問題實際上是著名的圖著色問題。若將每一個活動作為圖的一個頂點，不相容活動間用邊相連。使相鄰頂點著有不同顏色的最小著色數(shù)，相應于要找的最小會場數(shù)。) 數(shù)據(jù)輸入：由文件input.txt給出輸入數(shù)據(jù)。第一行有1個正整數(shù)k，表示有k個待安排的活動。接下來的k行中，每行有2個正整數(shù)，分別表示k個待安排的活動開始時間和結(jié)束時間。時間以0點開始的分鐘計。結(jié)果輸出：將編程計算出的最少會場數(shù)輸出到文件output.txt。會場安排問題的C+代碼：#include using namespace std;int Partition(int a, int low, int high )/劃分int i,j;int x = alow;i = low;j = high;while(ij) while(ij&x aj) j = j - 1; if(ij) ai = aj; i=i+1; while(i= ai) i = i + 1; if(ij) aj = ai; j=j-1; ai = x; return i;void QuickSort(int a, int low, int high) int Position; if(low -1) n=1;for(;i=bs) /有一個活動結(jié)束，新活動可在已空閑的會場進行。 s+;else n+; /要增開一會場 return n;int main( ) int n; cinn; int *st= new intn; int *et=new intn; for(int i=0;istieti; QuickSort(st,0,n-1); QuickSort(et,0,n-1); cout schedule(st,et,0,n-1) endl; delete st; delete et; return 0;輸入文件示例輸出文件示例input.txt output.txt 5 3 1 23 12 28 25 35 27 80 36 50 編碼分析根據(jù)會場安排問題的定義，首先將問題簡化為：找出兩個活動，若ei和ej滿足sifj或sjfi，則稱這兩個活動相容，即問題轉(zhuǎn)化為：要求找出最多相容會場集合A。問題簡化為對相容會場A的尋找，下面用貪心方法分析過程，根據(jù)題意，選取一種量度標準，然后按量度標準對n個輸入排序，按順序一次輸入一個量。如果這個輸入和當前已構(gòu)成在這種量度意義下的部分最優(yōu)解加在一起不能產(chǎn)生一個可行解，則不把此輸入加到這部分解中，這種能夠得到某種量度意義下的最優(yōu)解的分級處理方法就是貪心方法。那么問題轉(zhuǎn)化為對度量標準的尋找，判斷各個數(shù)據(jù)是否可以包含在解向量中去，然后根據(jù)目標函數(shù)來選擇最優(yōu)解。貪心算法（1）將所有活動按結(jié)束時間排序，得到活動集合E=e1，e2，en；（2）先將e1選入結(jié)果集合A中，即A=e1；（3）依次掃描每一個活動ei：如果ei的開始時間晚于最后一個選入A的活動ej的結(jié)束時間，則將ei選入A中，否則放棄ei。最優(yōu)解證明若E=e1，e2en是按結(jié)束時間排序的活動集合，則e1具有最早的結(jié)束時間，設存在一個最優(yōu)安排A不包含e1，并以ei開始，則易見：A-eie1也是最優(yōu)的活動安排；依此類推，即可推出上述活動都為A中的不相容最優(yōu)活動。俗話所的好的：紙上得來終覺淺，絕知此事要躬行！那么讓我們舉個例子來進一步清晰化問題：下面表格有12個活動，并給出各個活動的開始時間與結(jié)束時間，那么請用上述貪心解法分析并求解最優(yōu)會場數(shù)