事件的調度算法

Question

我有一個事件的列表，每個事件都有一個持續時間。 我正在尋找一種算法來安排這些事件的一天。從上午9點到下午12點，然後從下午1點到不晚於4點，也不遲於下午5點。

我不知道什麼是解決這個問題的好方法。 由於可能有幾種可能的解決方案，我的第一個想法是測試隨機組合的正確性。

我想知道是否有更確定的解決方法。 感謝;）

EDIT

@svs 的事件的定時是在幾分鐘內，沒有事件應當重疊。 除了午餐休息時間從下午12點到下午1點，事件之間不需要暫停。

Answer 1

好吧既然你基本上有兩個相等的時隙桶，你可以基本上按順序安排它們，不管順序如何，並假設有一個解決方案，尋找你如何能夠把它們排除在外。提着水桶A和B.

開始放入桶A. 最大的活動E1再放入放入桶B中的最大事件是在最E1-E2分鐘之久鬥B. 下一個最大的事件e。繼續添加到B桶，直到B桶的總分鐘數不超過A。

然後重複上述（將B切換爲A）。

繼續重複上述過程，直到完成活動。

這隻會工作，因爲你的每個桶有相同的長度，180分鐘。

實際上，因爲你有這個4-5pm的規則，任何額外的事件都會留在最後。他們都會在一個桶裏，這將是下午的桶。如果由於某種原因你有一個大於180分鐘的事件，那麼這將會預訂下午。然後，如果你在早晨（從最大到最小）儘可能多的話，那麼其餘的就會在下午去。