我想做类似于 Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction). 的事情使用 Hopcroft-Karp 算法。但我的额外要求是我的时间间隔是重叠的。例如。时间段可以是上午 10 点至上午 11 点或上午 10 点 15 分至上午 11 点 15 分。 所以如果我选择上午 10 点到 11 点时段，我不想选择上午 10 点到 11 点 15 点时段。是否可以在不严重影响性能的情况下实现这一目标？
最佳答案
如果您使用某种流扩展器添加另一个级别区分时隙，则可以使用类似于您对 Hopcroft-Karp 提出的建议的流算法。
因此，源与人相关，人与时隙相关，时隙与时间分割相关，分割与接收器相关。
为了进一步描述分割，假设您有从 10:00、10:15、10:30 和 10:45 开始的时段。时间分割为 15 分钟。如果所有 session 都是一个小时，那么 10:00 时间段将连接到 10:00-10:15 分割以及 10:15-10:30、10:30-10:45 和 10:45 -11:00 故障。
在时隙和故障之间的连接处必须有一些修改的逻辑。这是因为它们必须是时隙输入与故障连接之间流量值的变化。这是因为每当一个人被分配到一个时间段(时间段流入 = 1)时，就会有多个流向分割(时间段流出 = 4，每个上面的例子)。
一个免责声明我还没有尝试过这个。如果您这样做，请告诉我们它是否有效/效果如何。
关于algorithm - 具有重叠时隙的 session 调度算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19797438/