资源调度问题

Question

我正在开发一个摩托车租赁网站。我遇到的问题是如何有效地解决将客人分配到摩托车上的问题。我知道如何以一种“愚蠢”的方式做到这一点，但我想知道是否有一个经典的算法来解决这类问题。这和给客人分配酒店房间的问题是一样的。在最后一个示例中，目标是通过从不因低效调度而拒绝预留来实现最大占用率。

我非常确定这个问题必须是一个经典的问题，并且有一个已知的解决方案。

非常感谢。

Answer 1

您感兴趣的是Interval Scheduling。假设所有预订都具有相同的权重(没有一个比其他任何一个更受青睐)，那么您将需要一个贪婪算法。

Here (pdf)是一些关于这个主题的很好的幻灯片。

基本上，您希望首先安排最早结束的预订。

Answer 2

这是间隔调度，但它是一个在线算法。如果你想进一步阅读，可以在这里阅读：

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