在两组人之间安排面试的算法

Question

我有两组人 - A组和B组。两组的大小相同，比如 n。

来自A组的人需要采访来自B组的m人，反之亦然，其中m < n。你可以想象这是两组之间的配对环节。

对于 Set A 和 Set B 中的每个人，他们已经与来自另一组的 m 人进行了预匹配，因此没有的预赛是重复。

如何安排 m 个时间段，这样

• 两组中的每一个 n 人在每个时间段采访另一组预先匹配的人
• 没有人会同时接受两次面试
• 在 m 个时段结束时，每个人都完成了赛前的所有采访

感谢任何帮助!

Answer 1

您可以将预匹配表示为图形，其中两个集合的成员表示为节点，匹配表示为无向边。这将是一个二分图，因为 A 的任何成员都与 A 的另一个成员不匹配(B 也是如此)。

然后，您想用 m 种颜色找到该图的边缘着色。边着色为每条边分配两种颜色，这样共享公共(public)节点的两条边都不会具有相同的颜色。如果我们假设颜色代表时间段，那么这就准确地转化为每个人在任何时间只能进行一次面试的要求。

这个问题有多种算法。看看 Wikipedia article供引用。