Ford Fulkerson algorithm Java

I need help implement an efficient algorithm for the following scheduling problem.

There are n patients coming to the hospital for health examination tomorrow, but there are only 2 doctors available (Doctor A and Doctor B). Each health exam takes 1 time slot for a doctor. If possible, I need to allocate those n patients to n time slots using only 1 doctor. If 1 doctor is not possible, I can assign maximum 2 doctors since only 2 doctors are available. If 2 doctors are still not enough. Simply output impossible

I'm taking patients' availability as input. For example, there are 5 patients, patient 1 is only available for time slot 1,2,5, patient 2 is available for time slot 3, 4, patient 3 is available for time slot 1......and so on.

P1: 1 2 5
P2: 3 4
P3: 1
P4: 2
P5: 3 5

In this case, I just need 1 doctor to do the job. output

P1: Time slot 5 - Doc A
P2: Time slot 4 - Doc A
P3: Time slot 1 - Doc A
P4: Time slot 2 - Doc A
P5: Time slot 3 - Doc A

If I get input like:

P1: 1 2 5
P2: 3 4
P3: 2
P4: 2
P5: 3 5

Then I'll need to assign both doctors since P3 and P4 have conflicts in availability. output:

P1: Time slot 5 - Doc A
P2: Time slot 4 - Doc A
P3: Time slot 2 - Doc A
P4: Time slot 2 - Doc B
P5: Time slot 3 - Doc A

What's the most efficient algorithm for problem like this? How can I implement Ford Fulkerson algorithm for this?

What I have done so far.

I was trying to store each patient's available time slots into separate arrays.

Sort the arrays by length. Assign the patient with the least available time slots first.

Once a patient is assigned, delete this time slot in the rest arrays and sort the arrays by length again.

Repeat this process until all patients are assigned.

Solution

Let's take a deeper look at this problem. We have a set patients, a set of time slots and some connections between them(availability of patients at a given time). It looks exactly like maximum matching problem in a bipartite graph! So the first set of vertices should correspond to patients(one vertex per one patient), the second set should correspond to time slots(one vertex per each time slot). There is an edge between a vertex from the first set and the vertex from the second set if and only if a patient is available at this time slot. If maximum matching size is equal to the number of patients then it one doctor is sufficient, otherwise no.

How to solve this problem for 2 doctors? Almost the same way. We can still construct bipartite graph for patients and time slots, but now we have 2 vertices in the second set for each time slot(one for the first doctor and the second for the other one). The edges are added in the same way too. And again all we need to check is that maximum matching size is equal to the number of patients.

To find maximum matching in a bipartite graph, you can use Dinic or Hopcroft-Karp algorithm to get O(M * sqrt(N)) time complexity, where N is the number of vertices and M is the number of edges.