algorithm - 预约调度算法(N人有N个忙闲槽，约束-满足)

Question

问题陈述

我们有一个雇主想要面试 N 个人，因此安排了 N 个面试时段。每个人都有这些时段的忙闲时间表。给出一个算法，如果可能的话将 N 个人安排到 N 个槽位，如果不可能则返回一个标志/错误/等。最快的运行时复杂度是多少？

我目前的做法

天真:有N个!安排N个人的方法。遍历所有这些，对于每个排列，检查它是否可行。 O(n!)

回溯:

1. 寻找任何只能有 1 人的面试时间段。安排人员，将他们从候选人列表中删除并删除插槽。
2. 寻找任何只能进入 1 个空位的候选人。安排人员，将他们从候选人列表中删除并删除插槽。
3. 重复 1 和 2，直到不再有这样的组合。
4. 挑选一个人，将他们随机安排到一个可用的空档中。记住这个操作。
5. 重复 1、2、3，直到我们有一个时间表或存在无法解决的冲突。如果我们有时间表，请返回。如果存在无法解决的冲突，请回溯。

这是 O( n! ) 最坏的情况，我认为 - 这也好不到哪里去。

可能会有一个 D.P.解决方案 - 但我还没有看到它。

其他想法

该问题可以表示为一个 NxN 矩阵，其中行是“插槽”，列是“人”，值为“1”表示空闲，“0”表示忙碌。然后，我们在这个矩阵中寻找行列交换的单位矩阵。第 1 步和第 2 步正在寻找只有一个“1”的行或列。 (如果矩阵的秩=N，则表示有解。反之则不成立)另一种看待它的方法是将矩阵视为未加权的有向图边矩阵。然后，每个节点代表 1 个候选者和 1 个槽位。然后我们正在寻找一组边，以便图中的每个节点都有一个传出边和一个传入边。或者，如果有 2 个节点，它将是一个二分图。

矩阵示例:

1 1 1 1
0 1 1 0
1 0 0 1
1 0 0 1

Answer 1

正如你所指出的，这个问题相当于在二分图中寻找最大匹配的问题(一组顶点是人的集合，另一组是槽的集合，一个人之间有一条边以及一个空位(如果此人有空)。

这个问题可以用 Hopcroft-Karp algorithm 解决.

最坏情况下的复杂度为 O(n^(5/2))，如果图是稀疏的则更好。