加權區間調度與最小數量的工作要求

Question

問題是我有經典的加權區間調度問題，但有一個額外的要求。這個要求是，從給定的工作中，必須完成一定數量的工作。

我已經用bruteforce解決了它。但我需要更有效的解決方案。我用動態規劃解決了經典的加權排序問題，但是我不能。你有什麼建議嗎。謝謝你的建議。

Answer 1

只需添加基於經典的調度問題

該維度給出的就業人數多了一個維度迄今

如完成。

F [i] [j]是指在時間i，其中j工作已經完成，最大的利潤是什麼

F [i] [j]可以決定F [job_end_time [K] [J + 1]因爲job_start_time [k]> = i

Answer 2

那麼，我不明白這個問題與傳統的加權區間調度有什麼不同。如果「必須完成」的工作不會重疊（如果他們是那麼你有不明確的問題 - 如何選擇兩個重疊的「必須完成」的工作？），那麼你只需要一種方法來使他們的相對重量站立在其餘的工作中。

你可以在O（n）中遍歷你的工作，並找到最大的權重。然後，對於「必須完成」的工作，您需要將這個最大值添加到他們的權重中。這將確保他們將被選中而不是其他任何工作，因爲他們的相對權重肯定會高於非優先工作。

正如我所說的唯一的問題是何時「必須完成」作業重疊。因爲在那種情況下，你最終會選擇一些沒有選擇的工作（因爲你必須選擇一個工作而不是另一個）。