具有重叠时间段的会议安排算法

Question

我想使用Hopcroft-Karp算法做类似于约会安排算法（N个人和N个空闲繁忙时间段，约束满足）的事情。但我的额外要求是我的时间间隔有重叠。例如，时间段可以是上午10点到11点或上午10点15分到11点15分。因此，如果我选择了上午10点到11点的时间段，我就不想选择上午10点15分到11点15分的时间段。是否可能在不严重影响性能的情况下实现这一点？

- HarshJain

---

我也在寻找使用约束编程的解决方案。@hakank 似乎是这方面的专家！我找到的最接近的解决方案是：http://stackoverflow.com/questions/20631657/constraint-programming-scheduling-speakers-in-shortest-time/20645601?noredirect=1#20645601 - Marcus

Answer 1

如果您添加另一种区分时间段的流扩展器，就可以使用类似于Hopcroft-Karp的流算法来实现您提出的算法。因此，您将有一个源连接到人员，人员连接到时间段，时间段连接到时间细分，并将其连接到汇点。

为了进一步描述这些细分，假设您有从10:00、10:15、10:30和10:45开始的时间段。时间细分将在15分钟内完成。如果所有会议都持续一个小时，那么10:00时间段将与10:00-10:15细分以及10:15-10:30、10:30-10:45和10:45-11:00细分相连。

在时间段和细分之间的连接处需要进行一些修改后的逻辑。这是因为在时间段输入和连接到细分之间必须更改流值。这是因为每当一个人被分配到一个时间段（时间段流入=1）时，就会有多个流到细分（例如上面的时间段流出=4）。

免责声明：我没有尝试过这个方法。如果你尝试了，请告诉我们它的有效性如何。

- wckd