事件安排

Question

您將得到一組n工作。每項工作都與起始時間和結束時間相關聯，均以整數表示，並且您可以從中獲利。您必須確定採取哪些工作來實現利潤最大化，同時請記住，任何時候只能完成一項工作。有沒有一種算法，這比O（ñ）效率？

Answer 1

該算法：

鑑於集合S = {I1，I2，...，IN}：

• 排序根據從低到高的開始時間S中的間隔。

現在我們已經命令集{J1，J2，...，Jn}。 （以W1，W2，...，Wn作爲利潤）

我們將（i）定義爲最小指數k，這樣的起始時間Jk高於Ji的結束時間。如果沒有人存在，則返回-1。

將D [i]表示爲集合{Ji，Ji + 1，...，Jn}中的最大利潤（如您所述）。

所以我們得到：

D[-1] = 0; 
D[i] = maximum{D[i+1],Wi + D[a(i)]}. 

• 返回d [0]。

運行時間：

排序N個區間 - O（nlogn）。

構造D-O（n）。

整體運行時間= O（nlogn）。

Answer 2

您描述的問題稱爲加權間隔調度，可以在O（nlogn）步驟中解決 - 如果作業已經排序，甚至可以解決O（n）。

快速谷歌搜索將爲您提供所有您需要的信息。