问题陈述

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

到目前为止我的方法

天真：有N！安排N个人的方法。检查所有这些对象，对于每个排列，检查是否可行。上！ ）

回溯：

1. 查找任何只能有1个人的面试时隙。安排人员，将其从候选人列表中删除，然后删除空位。
2. 寻找只能进入1个插槽的任何候选人。安排人员，将其从候选人列表中删除，然后删除空位。
3. 重复1和2，直到没有其他类似的组合。
4. 选择一个人，将他们随机安排到其可用的插槽中。记住此操作。
5. 重复1、2、3，直到我们有了时间表或解决了无法解决的冲突。如果有时间表，请将其退回。如果存在无法解决的冲突，请回溯。

我认为这是O（n！）最坏的情况-没什么好了。

也可能有DP解决方案-但我还没有看到。

其他想法

问题可以用NxN矩阵表示，其中行是“插槽”，列是“人”，值分别为“ 1”（空闲）和“ 0”（忙）。然后，我们正在该矩阵内寻找行-
列交换的身份矩阵。步骤1和步骤2寻找仅包含一个“
1”的行或列。（如果矩阵的秩为N，则表示存在解决方案。但是相反的情况不成立）。另一种查看方法是将矩阵视为未加权的有向图边矩阵。然后，每个节点代表1个候选和1个时隙。然后，我们正在寻找一组边，以便图形中的每个节点都有一个输出边和一个输入边。或者，对于2x节点，它将是二部图。

矩阵示例：

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