小编Dar*_*der的帖子

问题陈述

我们有一个雇主想要采访N人,因此会有N个面试时段.每个人都有自由忙碌的时间表.给出一个算法,如果可能的话,将N个人调度到N个插槽中,如果不可能,则返回标志/错误/等.什么是最快的运行时复杂性？

到目前为止我的方法

天真:有N!安排N人的方法.浏览所有这些,对于每个排列,检查它是否可行.上! )

回溯:

1. 寻找任何只能有1个人的面试时间段.安排此人,将其从候选人列表中删除并删除该插槽.
2. 寻找任何只能进入1个位置的候选人.安排此人,将其从候选人列表中删除并删除该插槽.
3. 重复1和2,直到没有更多这样的组合.
4. 选择一个人,将他们随机安排到他们的一个可用插槽中.记住这个操作.
5. 重复1,2,3,直到我们有一个时间表或存在无法解决的冲突.如果我们有时间表,请将其退回.如果存在无法解决的冲突,请回溯.

这是O(n!)最糟糕的情况,我认为 - 这不是更好.

可能还有DP解决方案 - 但我还没有看到它.

其他想法

问题可以用NxN矩阵表示,其中行是"槽",列是"人",值是"1"表示空闲,"0"表示忙.然后,我们在这个矩阵中寻找一个行列交换的Identity Matrix.步骤1和2正在寻找只有一个"1"的行或列.(如果矩阵的秩是= N,那意味着有一个解决方案.但相反的情况并不成立)另一种看待它的方法是将矩阵视为未加权的有向图边缘矩阵.然后,每个节点代表1个候选和1个时隙.然后我们寻找一组边,以便图中的每个节点都有一个输出边和一个输入边.或者,对于2x节点,它将是一个二分图.

矩阵示例:

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

我试图通过散列一些节点指针来加速特定的链表操作.这是我正在使用的代码:

unordered_set< typename list< int >::iterator > myhashset;

在Visual Studio 2012中,我收到"错误C2338:C++标准不提供此类型的哈希",因为编译器不知道如何散列迭代器.因此,我需要为列表迭代器实现我自己的哈希函数,如下所示:

struct X{int i,j,k;};

struct hash_X{
  size_t operator()(const X &x) const{
    return hash<int>()(x.i) ^ hash<int>()(x.j) ^ hash<int>()(x.k);
  }
};

(维基百科参考)

我无法弄清楚迭代器的哪些成员保证唯一性(因此,我想要哈希的成员).另一个问题是那些成员可能是私人的.

想到的一个解决方案是重新实现和list :: iterator,但这看起来像是一个hack并引入了更多的代码来维护.