Algorithm to find unique set of items, one item from each of a set of sets

Question

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.

Answer 1

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.

Answer 2

Abhishek's answer will work for this problem, but I wanted to add an alternative that I've found to be faster. Abhishek has already mentioned (in passing) bipartite matching, to which the Hopcroft-Karp algorithm is relevant. The Hopcroft-Karp algorithm is used to find a maximum cardinality matching and runs in $O(sqrt(V)*E)$ time vs O(n^3) for the Hungarian algorithm. "Maximum cardinality matching" basically means it finds the maximum number of assignments that can be made, so in my earlier example the maximum number of people that can be scheduled in for a photograph based on everyone's availability and the available time slots of the photographer. So if the returned maximum cardinality equals the number of people, you know that an assignment is possible for everyone.

Note that the reason we can use the Hopcroft-Karp algorithm in this example is that we don't care about edge weightings -- it makes no difference who gets assigned to which timeslot, as long as everyone gets some timeslot. We would need something like the Hungarian algorithm if we did care about weightings, e.g. if we had an "inconvenience factor" that every person assigned to each of their available timeslots, as the Hungarian algorithm is designed to optimize the result under these conditions where as Hopcroft-Karp only determines how many assignments are possible at all.

In practice I started off using the Hungarian algorithm and it took ~30 seconds to execute on my particular dataset. After switching it out for the Hopcroft-Karp algorithm, I could produce the same result in < 1 second.