algorithm - 带有扭曲的二分匹配

Question

我正在处理将演讲者分配到时段的调度问题，演讲者的可用性各不相同。最大匹配未加权二分图适用于一个简单的解决方案，其中每个说话者都被分配到一个槽。

现在假设在有人发言的每个槽之后，应该有一个空槽(除了最后一个)。如何建模？

最后，当一些发言者应该连续发言时，可以使用图论吗？

谢谢

Answer 1

如果

• 每个可以参加奇数时段的演讲者也可以参加下一个(偶数)时段，并且
• 最多有一个演讲者需要连续 2 个席位，没有一个演讲者需要 3 个或更多，

然后一个非常简单的算法起作用:使用未加权的最大二分匹配，但只分配奇数槽，让每个偶数槽为空。如果某人需要 2 个连续的槽位，那么所有发生的事情就是，对于他/她之后的所有槽位对，槽位使用情况将被交换，以便奇数槽位留空并使用偶数槽位。