我正在开发一个摩托车租赁网站。我遇到的问题是如何高效地解决为客人分配摩托车的问题。我知道如何以“愚蠢”的方式做到这一点,但我想知道是否有一种经典算法可以解决此类问题。这与将客人分配到酒店房间是同样的问题。在最后一个示例中,目标是通过不因调度效率低下而拒绝预订来实现最大入住率。
我很确定这个问题一定是一个有已知解决方案的经典问题。
多谢。
你感兴趣的东西叫做间隔安排 http://en.wikipedia.org/wiki/Interval_scheduling。假设所有预订都具有相同的权重(没有一个比其他预订更受青睐),您需要一个贪婪算法。
在这里(pdf) http://www.cs.princeton.edu/~wayne/kleinberg-tardos/04greedy-2x2.pdf有一些关于该主题的不错的幻灯片。
基本上,您希望首先安排最早结束的预订。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)