用最長的作業時間安排時間表。

Question

我正在處理一些問題，我有一些時間設置（開始 - 結束），我必須給出清單，以便最大數量的工作完成。

1. 我有解決方案，我用DP和解決它的On2

可它在做什麼？

Answer 1

好吧，我得到了解決它可以通過貪心算法 做詳細說明： http://www.cs.umd.edu/class/fall2009/cmsc451/lectures/Lec04-interval.pdf

Answer 2

你讓出崗位是J1（S1，E1），J2（S2，E2），...，JN（ sn，en） 其中s1，s2，s3，...，sn是作業的開始時間，而e1，e2，e3，...，en是作業的結束時間。

現在工作根據其開始時間排序（SI的） （使用任何的算法（O（N LG N））。 還要注意作業＃（你或許可以存儲作業＃在另一個數組。 當您對作業的開始時間進行排序時，也會對相應的作業＃排列）

現在從列表中選擇最後一個作業（現在排序），並將其放入最終答案列表中。

從上一份作業 中以反向方式瀏覽列表，並在上一份作業有時繼續檢查可以執行的作業已經被採納。此作業的結束時間小於或等於上次作業的開始時間。將這份工作添加到您的最終答案列表中。

現在執行此作業的相同程序。從該索引中掃描列表並獲取工作，使其結束時間小於或等於上次添加到最終答案列表中的工作的開始時間。重複此操作直到完成。

現在只需計算最終答案列表中的作業數量。 這是可以完成的作業的最大數量。

整個過程需要O（n lg n）+ O（n）時間。 （如果您使用非基於比較的排序算法（如基數排序）對起始時間進行排序，則可以減少這一點，然後複雜度變爲O（n））。