在两组人之间安排面试的算法
Algorithm to schedule interviews between two sets of people
我有两组人——A组和B组。两组大小相同，比如 n.
来自A组的人需要采访m来自B组的人，副-反之亦然，其中 m < n。你可以想象这是两组之间的配对环节。
对于集合A和集合B中的每个人，他们已经与m[=来自另一组的 40=] 人使得 none 的预赛是 重复 .
如何安排 米 个时间段，以便
- 两组中的 n 人中的每一个在每个时间段采访另一组中他们预先匹配的人
- 没有人在同一时间段进行两次面试
- 在m个时段结束时，每个人都完成了赛前的所有采访
感谢任何帮助！
您可以将预匹配表示为图形，其中两个集合的成员表示为节点，匹配表示为无向边。这将是一个二分图，因为 A 的任何成员都与 A 的另一个成员不匹配（B 也是如此）。
然后，你想用 m 种颜色找到这个图的边缘着色。边着色为每条边分配两种颜色，这样共享公共节点的两条边都不会具有相同的颜色。如果我们假设颜色代表时间段，这就准确地转化为每个人在任何时间只能进行一次面试的要求。
这个问题有多种算法。查看 Wikipedia article 以获取一些参考。
首先创建匹配项
将数据集相对放置，并在相对的插槽之间进行直连。第一个匹配是1:1。然后，对于每个剩余的 m，将 B 向上（或向下）旋转一步并重新进行直连接。 n=7 和 m=1、2、3、4、5 和 6 的示例（一列对是一次采访时间）：
│A B│ │A B│A B│ │A B│A B│A B│ │A B│A B│A B│A B│ │A B│A B│A B│A B│A B│ │A B│A B│A B│A B│A B│A B│
├───┤ ├───┼───┤ ├───┼───┼───┤ ├───┼───┼───┼───┤ ├───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┤
│1 1│ │1 1│1 2│ │1 1│1 2│1 3│ │1 1│1 2│1 3│1 4│ │1 1│1 2│1 3│1 4│1 5│ │1 1│1 2│1 3│1 4│1 5│1 6│
│2 2│ │2 2│2 3│ │2 2│2 3│2 4│ │2 2│2 3│2 4│2 5│ │2 2│2 3│2 4│2 5│2 6│ │2 2│2 3│2 4│2 5│2 6│2 7│
│3 3│ │3 3│3 4│ │3 3│3 4│3 5│ │3 3│3 4│3 5│3 6│ │3 3│3 4│3 5│3 6│3 7│ │3 3│3 4│3 5│3 6│3 7│3 1│
│4 4│ │4 4│4 5│ │4 4│4 5│4 6│ │4 4│4 5│4 6│4 7│ │4 4│4 5│4 6│4 7│4 1│ │4 4│4 5│4 6│4 7│4 1│4 2│
│5 5│ │5 5│5 6│ │5 5│5 6│5 7│ │5 5│5 6│5 7│5 1│ │5 5│5 6│5 7│5 1│5 2│ │5 5│5 6│5 7│5 1│5 2│5 3│
│6 6│ │6 6│6 7│ │6 6│6 7│6 1│ │6 6│6 7│6 1│6 2│ │6 6│6 7│6 1│6 2│6 3│ │6 6│6 7│6 1│6 2│6 3│6 4│
│7 7│ │7 7│7 1│ │7 7│7 1│7 2│ │7 7│7 1│7 2│7 3│ │7 7│7 1│7 2│7 3│7 4│ │7 7│7 1│7 2│7 3│7 4│7 5│
不幸的是，上面的例子是最简单直接的方法。除此之外，还有许多其他方法，可能会产生大量不同的配对。例如，如果 n,m 为 7,3，则可以每轮旋转 B 数据集而不是一个位置，而是两个位置。或者，当 A 的中途时，指向 B 的指针可能有一个额外的偏移量。或者，如果 n 更大，则可以（可能 - 变得毛茸茸）让该偏移量加上 A 的后半部分的非一步B旋转。只要B不回绕，几乎一切皆有可能。 n与m相比越大，争夺的可能性就越大。
最终，A 和 B 不需要是从 1 开始排序的数字。它们可以是任何数字。
解决这个问题
一如既往，了解数据会有所帮助。如果知道匹配最初是如何创建的，则可以根据该知识做一些捷径和结论。例如，如果我知道匹配是按上述方式创建的，并且我知道 n 和 m，那么我只需创建正确的 table 并对给定的匹配执行 search/slot-in。
如果没有，可以使用 solver 或 Nico Schertlers 答案中维基百科文章中提到的一些空缺。就我而言，我通常懒得深入研究，所以如果数据似乎不会爆炸太多，我喜欢尝试暴力替代方案。
暴力破解意味着创建所有可能的组合，然后过滤满足条件的组合。
不幸的是，这是一个糟糕的 SO 答案（在浏览器中等待两周），因为我现在没有时间深入研究解决方案。对不起。希望以后能完成。
我有两组人——A组和B组。两组大小相同，比如 n.
来自A组的人需要采访m来自B组的人，副-反之亦然，其中 m < n。你可以想象这是两组之间的配对环节。
对于集合A和集合B中的每个人，他们已经与m[=来自另一组的 40=] 人使得 none 的预赛是 重复 .
如何安排 米 个时间段，以便
- 两组中的 n 人中的每一个在每个时间段采访另一组中他们预先匹配的人
- 没有人在同一时间段进行两次面试
- 在m个时段结束时，每个人都完成了赛前的所有采访
感谢任何帮助！
您可以将预匹配表示为图形，其中两个集合的成员表示为节点，匹配表示为无向边。这将是一个二分图，因为 A 的任何成员都与 A 的另一个成员不匹配（B 也是如此）。
然后，你想用 m 种颜色找到这个图的边缘着色。边着色为每条边分配两种颜色，这样共享公共节点的两条边都不会具有相同的颜色。如果我们假设颜色代表时间段，这就准确地转化为每个人在任何时间只能进行一次面试的要求。
这个问题有多种算法。查看 Wikipedia article 以获取一些参考。
首先创建匹配项
将数据集相对放置，并在相对的插槽之间进行直连。第一个匹配是1:1。然后，对于每个剩余的 m，将 B 向上（或向下）旋转一步并重新进行直连接。 n=7 和 m=1、2、3、4、5 和 6 的示例（一列对是一次采访时间）：
│A B│ │A B│A B│ │A B│A B│A B│ │A B│A B│A B│A B│ │A B│A B│A B│A B│A B│ │A B│A B│A B│A B│A B│A B│
├───┤ ├───┼───┤ ├───┼───┼───┤ ├───┼───┼───┼───┤ ├───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┤
│1 1│ │1 1│1 2│ │1 1│1 2│1 3│ │1 1│1 2│1 3│1 4│ │1 1│1 2│1 3│1 4│1 5│ │1 1│1 2│1 3│1 4│1 5│1 6│
│2 2│ │2 2│2 3│ │2 2│2 3│2 4│ │2 2│2 3│2 4│2 5│ │2 2│2 3│2 4│2 5│2 6│ │2 2│2 3│2 4│2 5│2 6│2 7│
│3 3│ │3 3│3 4│ │3 3│3 4│3 5│ │3 3│3 4│3 5│3 6│ │3 3│3 4│3 5│3 6│3 7│ │3 3│3 4│3 5│3 6│3 7│3 1│
│4 4│ │4 4│4 5│ │4 4│4 5│4 6│ │4 4│4 5│4 6│4 7│ │4 4│4 5│4 6│4 7│4 1│ │4 4│4 5│4 6│4 7│4 1│4 2│
│5 5│ │5 5│5 6│ │5 5│5 6│5 7│ │5 5│5 6│5 7│5 1│ │5 5│5 6│5 7│5 1│5 2│ │5 5│5 6│5 7│5 1│5 2│5 3│
│6 6│ │6 6│6 7│ │6 6│6 7│6 1│ │6 6│6 7│6 1│6 2│ │6 6│6 7│6 1│6 2│6 3│ │6 6│6 7│6 1│6 2│6 3│6 4│
│7 7│ │7 7│7 1│ │7 7│7 1│7 2│ │7 7│7 1│7 2│7 3│ │7 7│7 1│7 2│7 3│7 4│ │7 7│7 1│7 2│7 3│7 4│7 5│
不幸的是，上面的例子是最简单直接的方法。除此之外，还有许多其他方法，可能会产生大量不同的配对。例如，如果 n,m 为 7,3，则可以每轮旋转 B 数据集而不是一个位置，而是两个位置。或者，当 A 的中途时，指向 B 的指针可能有一个额外的偏移量。或者，如果 n 更大，则可以（可能 - 变得毛茸茸）让该偏移量加上 A 的后半部分的非一步B旋转。只要B不回绕，几乎一切皆有可能。 n与m相比越大，争夺的可能性就越大。
最终，A 和 B 不需要是从 1 开始排序的数字。它们可以是任何数字。
解决这个问题
一如既往，了解数据会有所帮助。如果知道匹配最初是如何创建的，则可以根据该知识做一些捷径和结论。例如，如果我知道匹配是按上述方式创建的，并且我知道 n 和 m，那么我只需创建正确的 table 并对给定的匹配执行 search/slot-in。
如果没有，可以使用 solver 或 Nico Schertlers 答案中维基百科文章中提到的一些空缺。就我而言，我通常懒得深入研究，所以如果数据似乎不会爆炸太多，我喜欢尝试暴力替代方案。
暴力破解意味着创建所有可能的组合，然后过滤满足条件的组合。
不幸的是，这是一个糟糕的 SO 答案（在浏览器中等待两周），因为我现在没有时间深入研究解决方案。对不起。希望以后能完成。