I posted the same question on stackoverflow and immediately referred to post it here.
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(AX). A is the schedule table.
Is there any good way to do that?
- Possible approaches 2: solve as a 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:
- Find the candidate A which has minimum number of available time slots.
- Among the time slots when A is available, find the slot a which has minimum number of candidates who are possible to attend.
- Place A on slot a. Remove both from the table.
- 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.