Best algorithm for scheduling interviews

Question

I want to think about the best algorithm which let the interviewer meet maximum number of candidates. Suppose that there are n candidates and one interviewer. Each of interview will be held for a fixed time, so we can consider that each interview to be given a time slot. Number of time slots are given as m. All candidates are asked to submit whether they are available for each time slots. If I put it in table format, it looks like this.

1: available
0: not available

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

• Possible approaches 1: solve as a matrix problem

If I interpret this as a matrix problem, it would be reduced to find the Matrix X, expressed as a product of matrices with only one-to-one column exchange, that maximizes trace(AXI). A is the schedule table, and I is the identity matrix.

Is there any good way to do that?

• Possible approaches 2: solve as an algorithm problem

If one can think about the best algorithm which always produces best result, it does not necessarily be a matrix problem One that comes to my mind will be something like that:

1. Find the candidate A which has minimum number of available time slots.
2. Among the time slots when A is available, find the slot a which has minimum number of candidates who are possible to attend.
3. Place A on slot a. Remove both from the table.
4. Repeat above procedure for each candidates.

In the Python code format, it may look like this.

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

However, I can think many ways this algorithm would fail or may not be provide the best answers. I would be happy if anyone facing similar problem knows better ways to do that.

Answer 1

You can use maximum bipartite matching but this is quite similar to interval colouring so using that might be more efficient.

Sort the intervals by their start times, breaking ties arbitrarily
Let I_1, I_2,..., In denote the intervals in this order
For j = 1, 2, 3, ... , n
  For each interval I_i that precedes I_j in sorted order and overlaps it
    Exclude the label of I_i from consideration for I_j
  Endfor
  If there is any label from {1, 2,..., d} that has not been excluded then
    Assign a nonexcluded label to I_j
  Else
    Leave I_j unlabeled
  Endif
Endfor

This is the pseudocode for the algorithm from Algorithm Design by K&T p.g. 124