部分重疊時間的加權活動選擇

Question

讓我們假設我們有n個時間表。每個時間表我有一個權重w（i），準備時間準備（i）和休息時間休息（i）。準備時間意味着如果我們選擇時間表i，我們不得不選擇時間表i - 準備（i），i - 準備（i）+ 1 ... i-1。

休息時間，也就是說，如果我們選擇shedule我，我們有責任不要選擇shedules + 1，I + 2 ... 1 +休息（我）

我們的任務是選擇按照適當的時間表上述限制，以使W最大化。

注意：對於i = 1，我們忽略prep（i）。我們假設我們已經準備好了。對於i = n wh忽略rest（i）。

限制：一個計劃的準備時間可能會與另一個計劃的休息時間重疊。舉個例子，如果我們有休息（5）= 2，準備（8）= 2，我們可以選擇兩個時間表。休息（5）= 2意味着如果我們選擇5，我們不允許選擇6和7。 Prep（8）= 2意味着如果我們選擇8，我們不能選擇6和7。所以我們可以選擇5和8.

什麼是最適合這項任務的算法？

如果不是限制，我們可以說每個時間表都有開始時間i - prep（i）和結束時間i + rest（i）。我們會有一個加權的活動選擇問題，所以我們可以用貪婪算法得到最優的O（nlogn）。但限制破壞了我的計劃。

Answer 1

讓f(i)成爲最佳答案，這樣i-th活動是最後一個活動。如果j < prep(i)和j + rest(j) < i，我們可以從活動j到活動i。換句話說，f(i) = (max of f(j) among all valid j such that j < prep(i) and j + rest(j) < i) + 1。這個公式導致了一個簡單的O(N^2)解決方案。

但我們可以做得更好！讓我們保持一個持久的分段樹，以獲得最大的操作（數組中每個位置的一個版本）。最初，它充滿了零。對於固定的i，我們使用prep(i) - 1版本並在[0, i - 1]範圍內執行最大查詢。然後f(i)是這個最大加1的值。之後，我們更新的f(i)位置樹（也就是創建一個新版本）。而已。

我們做O(N)得到最大值並且更新一個元素查詢到一個持久段樹，所以這個解決方案需要O(N log N)時間和空間，看起來不錯。但是，這似乎相當複雜。

現在讓我們擺脫持久性。當我們達到j = i + rest(i)（通過保持，比方說，在每個位置添加元素的向量），我們可以保留一個「正常」（即非持久性分段樹）並將其更新爲i和f(i)， 。我們不需要關心第二個限制。因此，f(i)是[0, prep(i) - 1]範圍內的最大值加1。找到f(i)後，我們推入i + rest(i)位置的待添加向量。

它仍然使用O(N log N)時間，但空間複雜度現在是線性的，並且我們不再需要持久段樹（事實上，每次更新只能增加值，並且我們需要一個前綴的最大值，所以我們可以在這裏使用二元索引樹而不是段樹）。