Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
665 views
in Technique[技术] by (71.8m points)

graph - Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction)

Problem statement

We have one employer that wants to interview N people, and therefore makes N interview slots. Every person has a free-busy schedule for those slots. Give an algorithm that schedules the N people into N slots if possible, and return a flag / error / etc if it is impossible. What is the fastest possible runtime complexity?

My approaches so far

Naive: there are N! ways to schedule N people. Go through all of them, for each permutation, check if it's feasible. O( n! )

Backtracking:

  1. Look for any interview time slots that can only have 1 person. Schedule the person, remove them from the list of candidates and remove the slot.
  2. Look for any candidates that can only go into 1 slot. Schedule the person, remove them from the list of candidates and remove the slot.
  3. Repeat 1 & 2 until there are no more combinations like that.
  4. Pick a person, schedule them randomly into one of their available slots. Remember this operation.
  5. Repeat 1, 2, 3 until we have a schedule or there is an unresolvable conflict. If we have a schedule, return it. If there's an unresolvable conflict, backtrack.

This is O( n! ) worst case, I think - which isn't any better.

There might be a D.P. solution as well - but I'm not seeing it yet.

Other thoughts

The problem can be represented in an NxN matrix, where the rows are "slots", columns are "people", and the values are "1" for free and "0" for busy. Then, we're looking for a row-column-swapped Identity Matrix within this matrix. Steps 1 & 2 are looking for a row or a column with only one "1". (If the rank of the matrix is = N, I that means that there is a solution. But the opposite does not hold) Another way to look at it is to treat the matrix as an unweighed directed graph edge matrix. Then, the nodes each represent 1 candidate and 1 slot. We're then looking for a set of edges so that every node in the graph has one outgoing edge and one incoming edge. Or, with 2x nodes, it would be a bipartite graph.

Example of a matrix:

1 1 1 1
0 1 1 0
1 0 0 1
1 0 0 1
See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

As you pointed out, the problem is equivalent to the problem of finding a maximum matching in a bipartite graph (one set of vertices is the set of people and the other on the set of slots, there is an edge between a person and a slot if the person is available for this slot).

This problem can be solved with the Hopcroft-Karp algorithm.

Complexity O(n^(5/2)) in the worst case, better if the graph is sparse.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...