我有两组人 - A组和B组。两组的大小相同,比如 n。
来自A组的人需要采访来自B组的m人,反之亦然,其中m < n。你可以想象这是两组之间的配对环节。
对于 Set A 和 Set B 中的每个人,他们已经与来自另一组的 m 人进行了预匹配,因此没有的预赛是重复。
如何安排 m 个时间段,这样
- 两组中的每一个 n 人在每个时间段采访另一组预先匹配的人
- 没有人会同时接受两次面试
- 在 m 个时段结束时,每个人都完成了赛前的所有采访
感谢任何帮助!
最佳答案
您可以将预匹配表示为图形,其中两个集合的成员表示为节点,匹配表示为无向边。这将是一个二分图,因为 A 的任何成员都与 A 的另一个成员不匹配(B 也是如此)。
然后,您想用 m
种颜色找到该图的边缘着色。边着色为每条边分配两种颜色,这样共享公共(public)节点的两条边都不会具有相同的颜色。如果我们假设颜色代表时间段,那么这就准确地转化为每个人在任何时间只能进行一次面试的要求。
这个问题有多种算法。看看 Wikipedia article供引用。
关于在两组人之间安排面试的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55595100/