寻求最大化面试官对接人数的最优面试调度算法

有n位候选人和1位面试官，每场面试对应固定时长的时间槽，共m个时间槽。所有候选人需提交各时间槽的可参加情况，可用如下矩阵表示（1代表可参加，0代表不可参加）：

Aoi   Banri  ...   Nami
slot 1    1      1    ...    0
slot 2    0      1    ...    1
 .        .      .    .      .
 .        .      .     .     .
 .        .      .      .    .
slot m    0      1    ...    0

可行思路1：矩阵解法 #

将问题转化为矩阵问题：寻找仅由一对一列交换矩阵乘积构成的矩阵X，使得trace(AXI)最大化（其中A为调度矩阵，I为单位矩阵）。想请教可行的求解方法。

可行思路2：算法解法 #

尝试了一种贪心思路，但发现它存在失效或无法得到最优解的情况，现寻求更优方案。

贪心思路步骤 #

• 找到可参加时间槽最少的候选人A；
• 在A可参加的时间槽中，选出可参加候选人最少的时间槽a；
• 将A安排至时间槽a，从列表中移除二者；
• 重复上述步骤直至所有候选人处理完毕。

对应Python代码示例 #

d=[[Aoi, 1, 0, ..., 0
Banri, 1, 1, ..., 1
.
.
.
Nami,  0, 1, ..., 0
]]

d_reserved=[]

d_return=reserve_each(d, d_reserved)


def reserve_each(d, _reserved):
  d_summed = cal_sums(d) # add summ on rows and columns as the outermost row/column.
  d=d[np.argsort(d_summed[-1, :])]

  for i in range(n):
    di=d[i,1:]
    if np.max(di) < 0.1:
      if i > 1:
        researve_each(d[i-1:, :], d[:i-1,:])
      else:
        # alert!!! perhaps goes random?

    di=di[np.argmax(d[-1,1:]*d[i,1:])]

    first = 1
    for dij in di:
      if dij == 1:
        dij = dij*first
        first = 0        

    d[i,1:]=di

  return np.concatenate(d_reserved, d, axis=1))    


def cal_sums(d):
  d=np.concatenate(d, np.sum(d[:, 1:], axis=1))
  d_summed=np.concatenate(d_sorted, [0, np.sum(d[1, 1:], axis=0)])
  return d_summed

上述贪心算法存在诸多可能失效或无法得到最优解的情况，恳请有类似问题经验的人士提供更优方案。

内容的提问来源于stack exchange，提问作者iyui