現(xiàn)需要申請一些場地舉辦一批活動，每個活動有開始時間和結(jié)束時間。在同一個場地，如果一個活動結(jié)束之前，另一個活動開始，即兩個活動沖突。若活動A從1時間開始，5時間結(jié)束，活動B從5時間開始，8時間結(jié)束，則活動A和B不沖突。現(xiàn)要計算n個活動需要的最少場地數(shù)。

求解該問題的基本思路如下(假設(shè)需要場地數(shù)為m，活動數(shù)為n，場地集合為P₁，P₂，…，P_m)，初始條件Pi均無活動安排:

(1)采用快速排序算法對n個活動的開始時間從小到大排序，得到活動a₁，a₂，…，an。對每個活動a_i，i從1到n，重復(fù)步驟(2)、(3)和(4);

(2)從p₁開始，判斷a_i與P₁的最后一個活動是否沖突，若沖突，考慮下一個場地P₂，…;

(3)一旦發(fā)現(xiàn)a_i與某個P_j的最后一個活動不沖突，則將a_i安排到P_j，考慮下一個活動;

(4)若a_i與所有己安排活動的P_j的最后一個活動均沖突，則將a_i安排到一個新的場地，考慮下一個活動;

(5)將n減去沒有安排活動的場地數(shù)即可得到所用的最少場地數(shù)

算法首先采用了快速排序算法進行排序，其算法設(shè)計策略是(1);后面步驟采用的算法設(shè)計策略是(2)。整個算法的時間復(fù)雜度是(3)。下表給出了n=11的活動集合，根據(jù)上述算法，得到最少的場地數(shù)為(4)。

(1)A.分治

B.動態(tài)規(guī)劃

C.貪心

D.回溯

(2)A.分治

B.動態(tài)規(guī)劃

C.貪心

D.回溯

(3)A.Θ(lgn)

B.Θ(n)

C.Θ(nlgn)

D.Θ(n2)

(4)A.4

B.5

C.6

D.7

信管網(wǎng)參考答案：A、C、D、B

查看解析：www.xcpkj.com/st/3962326159.html

相關(guān)推薦：

點擊查看/下載：軟件設(shè)計師歷年真題匯總

點擊查看：軟件設(shè)計師在線培訓(xùn)課程 丨 免費試聽課程

免費練習(xí)：軟件設(shè)計師考試題庫(模擬試題、章節(jié)練習(xí)、每日一練)