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

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.

Leave a Comment