问题陈述
我们有一位雇主想要面试 N 个人，因此安排了 N 个面试时段。每个人都有一个空闲/忙碌的时间表。给出一个算法，如果可能的话，将 N 个人安排到 N 个位置，如果不可能，则返回一个标志/错误/等。最快的运行时复杂度是多少？
到目前为止我的方法
天真：有N个！安排N个人的方法。遍历所有这些，对于每个排列，检查它是否可行。在！ ）
回溯：
- 寻找只能有 1 人参加的面试时段。安排该人员，将其从候选人列表中删除并删除空位。
- 寻找只能进入 1 个位置的候选人。安排该人员，将其从候选人列表中删除并删除空位。
- 重复1和2，直到不再有类似的组合。
- 选择一个人，将他们随机安排到一个可用的位置。记住这个操作。
- 重复1、2、3，直到我们有一个时间表或存在无法解决的冲突。如果我们有时间表，请将其返回。如果有无法解决的冲突，就原路返回。
我认为这是 O( n! ) 最坏情况 - 这也好不到哪去。
可能有一个 D.P.解决方案以及 - 但我还没有看到它。
其他想法
该问题可以用 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
正如您所指出的，这个问题相当于在二部图中找到最大匹配的问题（一组顶点是人的集合，另一组顶点是槽的集合，人和槽之间有一条边如果此人可以胜任该时段）。
这个问题可以通过以下方法解决Hopcroft-Karp算法 http://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm.
最坏情况下的复杂度为 O(n^(5/2))，如果图稀疏，则更好。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
