Lazy bartender problem

There are N number of possible drinks.(n1,n2…)
Has C number of fixed customers.
Every customer has fixed favourite 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)

Need help on this question. If anyone can provide the approach or code it would be helpful in C++

1 Like

It is very similar to Bin Packing problem…
Consider allowed drinks as possible weights a bin can handle…

It is a NP hard problem… So you can try approximate algorithm mentioned above…

1 Like