I'm trying to find a "bartender algorithm"

Question

I was solving some example questions from an old programming contest. In this question we get an input of how many bartender we have, and which recipe's they know. Each cocktail takes 1 minute to make and we need to calculate if the order can be finished within 5 minutes, using all bartenders.

The key to solving this problem is assigning cocktails as efficient as possible. And thats where I'm stuck, my current algorithm gives the order to the bartender who knows the least other recipes. But of course this isn't 100% correct yet. Could anyone point me in the right direction (or give me an algorithm name to google) which solves this "bartender problem"?

Answer 1

This could be solved with a flow network.

• The source has edges to each bartender, with capacity 5.
• Each bartender have edges to each drink he/she can make, with capacity 5.
• Each drink have edges to the sink, with a capacity corresponding to the number that is ordered.

Compute the maximum flow from the source to the sink. If any order remains unfulfilled, there is no solution.