事件调度算法

Question

我有一个事件列表，每个事件都有一个持续时间。我想写一个算法来安排这些活动一天。上午九时至下午十二时，下午一时至下午四时及不迟於下午五时

我不确定什么是解决这个问题的好办法。由于可能有几个可能的解决方案，我的第一个想法是测试随机组合的正确性。

我想知道是否有更明确的方法来解决这个问题。(谢谢;)

编辑

@svs事件的时间以分钟为单位，任何事件都不应重叠。此外，除了中午12点到下午1点的午休时间外，没有必要暂停活动之间的活动。

Answer 1

好的，因为你基本上有两个相等的时隙桶，你基本上可以把它们都按顺序排好，不管顺序如何，假设有一个解决方案，看看你怎样才能把它们平平。从桶A和B开始。

将最大的事件e1放在桶A中，然后将下一个最大的事件e2放在桶B中，将最大的事件放在桶B中，最长为e1-e2分钟。继续添加到桶B，直到你的桶B没有超过A的总分钟。

然后重复上面的步骤，(切换A到B)。

继续重复上面的内容，直到你完成你的事件。

这只会起作用，因为你每个水桶有相同的长度，180分钟。

事实上，由于你有这个下午4点到下午5点的规则，任何额外的事件都会在最后留下。他们都在一个桶里，这就是下午的水桶。如果由于某种原因，你有一个活动是> 180分钟，那就预订下午。然后，如果你尽可能多的在早上(从最大到最小)，那么其余的将在下午。