Given a bitarray such as the following:

                      
         C0      C1      C2      C3     C4      C5
      **********************************************
   P0 *  0       0       1       0       1       0 *
   P1 *  0       1       0       0       1       0 *
   P2 *  0       0       0       1       1       0 *
   P3 *  1       0       0       0       0       1 *
   P4 *  0       0       0       0       0       0 *
   P5 *  0       0       0       0       0       0 *
   P6 *  1       0       0       0       0       0 *
      **********************************************

Each row represents a different person P_i, while each column represent a different color C_j. If a given cell A[i][j] is 1, it means that person i would like color j. A person can only get one color, and a color can only be given to one person.

In general, the number of people P > 0, and the number of colors C >= 0.

How can I, time-efficiently, compute the maximal amount of people who can get a color that they want?

The correct answer to the example above would be 5.

1. Person 6 (P6) only has one wish, so he gets color 0 (C0)
2. Since C0 is now taken, P3 only has one wish left, so he gets C5.
3. P0 gets C2, P1 gets C1 and P2 gets C3.

My first idea was a greedy algorithm, that simply favored the person (i.e. row) with the lowest amount of wanted colors. This works for the most part, but is simply too slow for my liking, as it runs in O(P*(P*C)) time, which is equal to O(n^3) when n = P = C. Any ideas to an algorithm (or another data structure) that can solve the problem quicker?

This might be a duplicate of another similar question, but I had trouble with finding the correct name for the type of problem, so bear with me if this is the case.

CodePudding user response：

This is a classical problem known as maximum cardinality bipartite matching . Here, you have a bipartite graph where in one side you have the vertices corresponding to the people and on the other side the vertices corresponding to the colors. An edge between a person and a color exists if there is a one in the corresponding entry in the matrix.

In the general case, the best known algorithms has worst case performance O(E*sqrt(V)), where E is the number of edges in the graph and V is the number of vertices. One such algorithm is called Hopcroft-Karp. I would suggest you to read the Wikipedia explanation that I linked.