資源調度問題

Question

我正在開發摩托車租賃網站。我遇到的問題是如何以有效的方式解決客人給摩托車的問題。我知道如何以一種「愚蠢」的方式做到這一點，但我想知道是否有一種經典的算法來解決這類問題。這與將客人分配給酒店客房的問題相同。在這最後一個例子中，我們的目標是通過永不拒絕預約而實現最大佔用率，因爲調度效率低下。

我很確定這個問題必須是一個已知解決方案的經典問題。

非常感謝。

Answer 1

您感興趣的內容叫做Interval Scheduling。假設所有預訂都具有相同的權重（沒有任何優惠比其他任何優惠），您需要一個貪婪算法。

Here (pdf)是關於該主題的一些很好的幻燈片。

基本上，您想先安排最早的結束預訂。

Answer 2

這是間隔調度，但它是一個在線算法。如果您想進一步閱讀，你可以在這裏閱讀：

http://www-bcf.usc.edu/~dkempe/teaching/online.pdf