活動(dòng)選擇問題是指若干個(gè)具有競(jìng)爭(zhēng)性的活動(dòng)要求互斥使用某一公共資源時(shí)，如何選擇最大的相容活動(dòng)集合。假設(shè)有一個(gè)需要使用某一資源（如場(chǎng)地等）的N個(gè)活動(dòng)組成的集合S={a1, a2, ... , an}，該資源一次只能被一個(gè)活動(dòng)占用。每個(gè)活動(dòng)ai有一個(gè)開始時(shí)間si和結(jié)束時(shí)間fi，且0≤si≤fi＜∞。一旦被選擇后，活動(dòng)ai就占據(jù)半開時(shí)間區(qū)間[si,fi)。如果兩個(gè)活動(dòng)ai和aj的時(shí)間區(qū)間互不重疊，則稱活動(dòng)ai和aj是兼容的。活動(dòng)選擇問題就是要選擇出一個(gè)由互相兼容的活動(dòng)組成的最大子集合。考慮下表中的活動(dòng)集合，其中各活動(dòng)采用歸并排序算法進(jìn)行遞增排序。從表中可以看到，子集{a3,a9,a11}由相互兼容的活動(dòng)組成。然而，它不是最大的子集，子集{a1,a4,a8,a11}更大，事實(shí)上，{a1,a4,a8,a11}是一個(gè)最大的相互兼容活動(dòng)子集。另外，還有一個(gè)最大子集是{a2,a4,a9,a11}

定義集合sij={ak∈s:fi≤sk＜fk≤sj}。為了完整地表示問題，加入兩個(gè)虛擬活動(dòng)， a0和an+1，其中，f0=0,sn+1=∞，這樣s =s0,n+1。

對(duì)于任一非空子問題sij，設(shè)am是sij中具有最早結(jié)束時(shí)間的活動(dòng)。那么：

（1）活動(dòng)am在sij的某個(gè)最大兼容活動(dòng)子集中。

（2）子活動(dòng)sim為空，所以選擇am將使smi為唯一可能非空的子問題。

如需了解更多備考資料，可點(diǎn)擊下方資料下載處或聯(lián)系在線客服獲取。