Assume you have a set of people J, and you need to take a photo of each person. Their is only one photographer and the photographer has a finite set of times T (|T| > |J|) available to take each photograph. At any given time t drawn from T, the photographer can take only one photograph. Each person in J is only available to have their photograph taken for some subset of the times in T, though each person has been asked to elect at least one time they are available. Essentially, based on each person's availability, the photographer wants to try and assign one person to each available timeslot in T such that everybody can get their photo taken. Is there a polynomial time algorithm to solve this problem? If not, what non-polynomial time problem reduces to this problem in polynomial time, i.e. how can it be shown that this problem is not in P?
Example:
The photographer is available at times [1, 12, 15, 33, 45, 77].
Person A is available at times [12, 33].
Person B is available at times [1, 12].
Person C is available at times [1, 12].
We can photograph everyone with the selection:
Person A: 33
Person B: 1
Person C: 12
If we were to start by choosing A: 12, B: 1, we would not be able to find a place for C, i.e. we'd have to backtrack and reassign A to 33.
Essentially I'm looking for a polynomial time algorithm to find an appropriate assignment of times if one exists, and otherwise be able to report that an appropriate assignment does not exist.
This can be modelled as an Assignment Problem (or Bipartite Graph matching problem).
The sources shall be people and destinations shall be the times available for photographer. The cost matrix can be built by making the cost of non-availability of a person at a time as 1, and availability as 0.
If the matrix is not a square one, then dummy people can be added with corresponding costs as 0. If the number of people is more than the number of times, then it is a case of impossible assignment.
If the resulting cost of an optimal solution is non-zero, it means that the assignment is not possible.
It can be solved using Hungarian Algorithm in polynomial time.