Lazy Bartender Algorithm

Question

I found following problem in one of the interviews. Please suggest me the algorithm for this. I don't need code.

• There are N number of possible drinks.(n1,n2..)
• Has C number of fixed customers.
• Every customer has fixed favorite set of drinks.
• Bartender has to create least possible number of drinks to suffice need of all the customers

Example:

Cust1: n3,n7,n5,n2,n9  
Cust2: n5  
Cust3: n2,n3  
Cust4: n4  
Cust5: n3,n4,n3,n5,n7,n4    

Output: 3(n3,n4,n5)  

Answer 1

Let's reformulate this problem. We have a bipartite graph G(Drinks, Customers, E). Where edge e(i, j) is in E when drink i is in the favorite set of the customer j. And we want to find the minimum cardinality subset of Drinks to cover all Customers set.

This problem is a variation of Set cover problem (look at the Hitting set formulation). It is known to be NP-hard, so there is no known polynomial algorithm.

Depending on constraints of the particular problem it can be solved with simple brute-force algorithm or dynamic programming/memoization approach, but you should know the exact constraints then.