事件的调度算法

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分钟的事件，那么这将会预订下午。然后，如果你在早晨（从最大到最小）尽可能多的话，那么其余的就会在下午去。