非加權區間調度的動態規劃算法？

Question

我想知道如果有人可以請幫我理解一個DP算法的不加權間隔調度。

我給了2個數組[t1，...，tn]和[d1，...，dn]，其中ti是工作i的開始時間，di是工作i的持續時間。此外，作業按開始時間排序，所以t1 < = t2 < = ... < = tn。我需要最大限度地增加可以執行而沒有任何重疊的作業數量。我試圖想出一個針對這個問題的DP算法和運行時。任何幫助將非常感激！

謝謝！

Answer 1

對不起，我現在沒有更多時間花在這個問題上了。這是一個想法，我認爲它很適合動態編程。 [其實我覺得這是DP，但近二十年過去了，因爲我最後研究這樣的事情...]

假設T = {t1, t2, ..., tn}如下劃分：

T = {t1, t2, ..., tn} = {t1, t2, ..., tk} U {tk+1, tk+2, ..., tn} 
    = T1(k) U T2(k) 

讓T2'(k)是的子集T2(k)不包含作業重疊T1(k)。

讓opt(X)成爲T的子集X的最佳值。然後

opt(T) = min(opt(T1(k)) + opt(T2'(k)) 

其中最小沿任何可能的k in {1, 2, ..., n}

當然採取你需要計算opt()遞歸，並考慮到重疊。

希望這會有所幫助！

Answer 2

對於我來說，考慮一下我是否最容易想到，如果我計算出每項工作的最終時間，並將工作分類爲增加結束時間的順序，儘管使用工作的開始時間可能會達到同樣的效果在相反的方向。

以增加結束時間的順序考慮每項工作。對於每項工作，如果你決定從事這項工作，你可以處理最多的工作，包括那份工作。要解決這個問題，請查看已經計算出的覆蓋時間直到該作業的開始時間的答案，並找到覆蓋最多作業數量的答案。在處理你正在考慮的工作時，你所能做的最好的就是最大數量。

當您考慮了所有工作時，您可以覆蓋的最大數量是您在考慮任何工作時計算的最大數量。通過存儲您在確定特定作業可能的最高分數時識別的上一個作業，然後從作業中以最高分數回溯這些指針，可以計算出要完成的作業。

隨氮素的工作考慮你最多N次先前計算的答案工作了每個職位的最佳可能得分的時候回頭看，所以我認爲這是O（N^2）