Bartender Drink Optimization
MediumUpdated: Aug 9, 2025
Problem
At a popular bar, each customer has a set of favorite drinks, and will happily accept any drink among this set. For example, in the following situation, customer 0 will be satisfied with drinks 0, 1, 3, or 6.
A lazy bartender working at this bar is trying to reduce his effort by limiting the drink recipes he must memorize. Given a dictionary input such as the one above, return the fewest number of drinks he must learn in order to satisfy all customers.
Examples
Example 1
Input: {0: [0, 1, 3, 6], 1: [1, 4, 7], 2: [2, 4, 7, 5], 3: [3, 2, 5], 4: [5, 8]}
Output: 2
Explanation: Drinks 1 and 5 will satisfy everyone. Customer 0 gets drink 1, customers 1 and 2 can get drinks 1 or 5, customer 3 gets drink 5, and customer 4 gets drink 5.
Example 2
Input: {0: [1, 2], 1: [2, 3], 2: [3, 4]}
Output: 2
Explanation: We need drinks 2 and 3. Customer 0 gets drink 2, customer 1 can get drink 2 or 3, and customer 2 gets drink 3.
Example 3
Input: {0: [1], 1: [2], 2: [3]}
Output: 3
Explanation: Each customer has only one preferred drink, so we need all three drinks: 1, 2, and 3.
Example 4
Input: {0: [1, 2, 3], 1: [1, 2, 3], 2: [1, 2, 3]}
Output: 1
Explanation: All customers like the same drinks, so we only need one drink (e.g., drink 1) to satisfy everyone.
Example 5
Input: {}
Output: 0
Explanation: No customers means no drinks needed.
Solution
Method 1 - Greedy Set Cover
Intuition
This is a classic set cover problem where we want to find the minimum number of drinks (sets) that cover all customers. We can use a greedy approach: repeatedly choose the drink that satisfies the most unsatisfied customers until all customers are covered.
Approach
- Create a mapping of drinks to the customers they satisfy
- Keep track of unsatisfied customers
- Greedily select the drink that covers the most remaining customers
- Remove satisfied customers from the unsatisfied set
- Repeat until all customers are satisfied
- Return the count of selected drinks
Code
C++
class Solution {
public:
int minDrinks(unordered_map<int, vector<int>>& preferences) {
if (preferences.empty()) return 0;
// Build drink to customers mapping
unordered_map<int, vector<int>> drinkToCustomers;
unordered_set<int> allCustomers;
for (auto& [customer, drinks] : preferences) {
allCustomers.insert(customer);
for (int drink : drinks) {
drinkToCustomers[drink].push_back(customer);
}
}
unordered_set<int> unsatisfied = allCustomers;
int drinkCount = 0;
while (!unsatisfied.empty()) {
// Find drink that covers most unsatisfied customers
int bestDrink = -1;
int maxCovered = 0;
for (auto& [drink, customers] : drinkToCustomers) {
int covered = 0;
for (int customer : customers) {
if (unsatisfied.count(customer)) {
covered++;
}
}
if (covered > maxCovered) {
maxCovered = covered;
bestDrink = drink;
}
}
// Remove satisfied customers
if (bestDrink != -1) {
for (int customer : drinkToCustomers[bestDrink]) {
unsatisfied.erase(customer);
}
drinkCount++;
}
}
return drinkCount;
}
};
Go
func minDrinks(preferences map[int][]int) int {
if len(preferences) == 0 {
return 0
}
// Build drink to customers mapping
drinkToCustomers := make(map[int][]int)
allCustomers := make(map[int]bool)
for customer, drinks := range preferences {
allCustomers[customer] = true
for _, drink := range drinks {
drinkToCustomers[drink] = append(drinkToCustomers[drink], customer)
}
}
unsatisfied := make(map[int]bool)
for customer := range allCustomers {
unsatisfied[customer] = true
}
drinkCount := 0
for len(unsatisfied) > 0 {
// Find drink that covers most unsatisfied customers
bestDrink := -1
maxCovered := 0
for drink, customers := range drinkToCustomers {
covered := 0
for _, customer := range customers {
if unsatisfied[customer] {
covered++
}
}
if covered > maxCovered {
maxCovered = covered
bestDrink = drink
}
}
// Remove satisfied customers
if bestDrink != -1 {
for _, customer := range drinkToCustomers[bestDrink] {
delete(unsatisfied, customer)
}
drinkCount++
}
}
return drinkCount
}
Java
class Solution {
public int minDrinks(Map<Integer, List<Integer>> preferences) {
if (preferences.isEmpty()) return 0;
// Build drink to customers mapping
Map<Integer, List<Integer>> drinkToCustomers = new HashMap<>();
Set<Integer> allCustomers = new HashSet<>();
for (Map.Entry<Integer, List<Integer>> entry : preferences.entrySet()) {
int customer = entry.getKey();
allCustomers.add(customer);
for (int drink : entry.getValue()) {
drinkToCustomers.computeIfAbsent(drink, k -> new ArrayList<>()).add(customer);
}
}
Set<Integer> unsatisfied = new HashSet<>(allCustomers);
int drinkCount = 0;
while (!unsatisfied.isEmpty()) {
// Find drink that covers most unsatisfied customers
int bestDrink = -1;
int maxCovered = 0;
for (Map.Entry<Integer, List<Integer>> entry : drinkToCustomers.entrySet()) {
int drink = entry.getKey();
List<Integer> customers = entry.getValue();
int covered = 0;
for (int customer : customers) {
if (unsatisfied.contains(customer)) {
covered++;
}
}
if (covered > maxCovered) {
maxCovered = covered;
bestDrink = drink;
}
}
// Remove satisfied customers
if (bestDrink != -1) {
for (int customer : drinkToCustomers.get(bestDrink)) {
unsatisfied.remove(customer);
}
drinkCount++;
}
}
return drinkCount;
}
}
Python
class Solution:
def min_drinks(self, preferences: Dict[int, List[int]]) -> int:
if not preferences:
return 0
# Build drink to customers mapping
drink_to_customers = {}
all_customers = set(preferences.keys())
for customer, drinks in preferences.items():
for drink in drinks:
if drink not in drink_to_customers:
drink_to_customers[drink] = []
drink_to_customers[drink].append(customer)
unsatisfied = set(all_customers)
drink_count = 0
while unsatisfied:
# Find drink that covers most unsatisfied customers
best_drink = -1
max_covered = 0
for drink, customers in drink_to_customers.items():
covered = sum(1 for customer in customers if customer in unsatisfied)
if covered > max_covered:
max_covered = covered
best_drink = drink
# Remove satisfied customers
if best_drink != -1:
for customer in drink_to_customers[best_drink]:
unsatisfied.discard(customer)
drink_count += 1
return drink_count
Complexity
- ⏰ Time complexity:
O(d * c * n), where d is the number of unique drinks, c is the number of customers, and n is the average number of drinks per customer. In each iteration we check all drinks and their customers - 🧺 Space complexity:
O(d * c), for storing the drink-to-customers mapping and unsatisfied customer set
Method 2 - Bitmask Dynamic Programming
Intuition
For smaller inputs, we can use bitmask DP to find the exact minimum. Each customer can be represented by a bit, and each drink covers a specific subset of customers (represented as a bitmask). We find the minimum number of drinks needed to cover all customer bits.
Approach
- Convert customer preferences to bitmasks where each drink covers certain customer bits
- Use DP where
dp[mask]represents minimum drinks needed to satisfy customers in the mask - For each state, try adding each possible drink and update the resulting state
- Return
dp[(1 << num_customers) - 1]which represents all customers satisfied
Code
C++
class Solution {
public:
int minDrinks(unordered_map<int, vector<int>>& preferences) {
if (preferences.empty()) return 0;
// Map customers to indices
vector<int> customers;
unordered_map<int, int> customerToIndex;
for (auto& [customer, _] : preferences) {
customerToIndex[customer] = customers.size();
customers.push_back(customer);
}
int n = customers.size();
if (n > 20) return greedySolution(preferences); // Fallback for large inputs
// Build drink masks
unordered_map<int, int> drinkMasks;
for (auto& [customer, drinks] : preferences) {
int customerBit = 1 << customerToIndex[customer];
for (int drink : drinks) {
drinkMasks[drink] |= customerBit;
}
}
// DP: dp[mask] = min drinks to satisfy customers in mask
vector<int> dp(1 << n, INT_MAX);
dp[0] = 0;
for (int mask = 0; mask < (1 << n); mask++) {
if (dp[mask] == INT_MAX) continue;
for (auto& [drink, drinkMask] : drinkMasks) {
int newMask = mask | drinkMask;
dp[newMask] = min(dp[newMask], dp[mask] + 1);
}
}
return dp[(1 << n) - 1];
}
private:
int greedySolution(unordered_map<int, vector<int>>& preferences) {
// Fallback to greedy for large inputs
unordered_map<int, vector<int>> drinkToCustomers;
unordered_set<int> allCustomers;
for (auto& [customer, drinks] : preferences) {
allCustomers.insert(customer);
for (int drink : drinks) {
drinkToCustomers[drink].push_back(customer);
}
}
unordered_set<int> unsatisfied = allCustomers;
int drinkCount = 0;
while (!unsatisfied.empty()) {
int bestDrink = -1;
int maxCovered = 0;
for (auto& [drink, customers] : drinkToCustomers) {
int covered = 0;
for (int customer : customers) {
if (unsatisfied.count(customer)) covered++;
}
if (covered > maxCovered) {
maxCovered = covered;
bestDrink = drink;
}
}
if (bestDrink != -1) {
for (int customer : drinkToCustomers[bestDrink]) {
unsatisfied.erase(customer);
}
drinkCount++;
}
}
return drinkCount;
}
};
Go
func minDrinksDP(preferences map[int][]int) int {
if len(preferences) == 0 {
return 0
}
// Map customers to indices
customers := make([]int, 0)
customerToIndex := make(map[int]int)
for customer := range preferences {
customerToIndex[customer] = len(customers)
customers = append(customers, customer)
}
n := len(customers)
if n > 20 {
return minDrinks(preferences) // Fallback to greedy
}
// Build drink masks
drinkMasks := make(map[int]int)
for customer, drinks := range preferences {
customerBit := 1 << customerToIndex[customer]
for _, drink := range drinks {
drinkMasks[drink] |= customerBit
}
}
// DP: dp[mask] = min drinks to satisfy customers in mask
dp := make([]int, 1 << n)
for i := range dp {
dp[i] = math.MaxInt32
}
dp[0] = 0
for mask := 0; mask < (1 << n); mask++ {
if dp[mask] == math.MaxInt32 {
continue
}
for _, drinkMask := range drinkMasks {
newMask := mask | drinkMask
if dp[mask] + 1 < dp[newMask] {
dp[newMask] = dp[mask] + 1
}
}
}
return dp[(1 << n) - 1]
}
Java
class Solution {
public int minDrinks(Map<Integer, List<Integer>> preferences) {
if (preferences.isEmpty()) return 0;
// Map customers to indices
List<Integer> customers = new ArrayList<>(preferences.keySet());
Map<Integer, Integer> customerToIndex = new HashMap<>();
for (int i = 0; i < customers.size(); i++) {
customerToIndex.put(customers.get(i), i);
}
int n = customers.size();
if (n > 20) return greedySolution(preferences); // Fallback for large inputs
// Build drink masks
Map<Integer, Integer> drinkMasks = new HashMap<>();
for (Map.Entry<Integer, List<Integer>> entry : preferences.entrySet()) {
int customer = entry.getKey();
int customerBit = 1 << customerToIndex.get(customer);
for (int drink : entry.getValue()) {
drinkMasks.put(drink, drinkMasks.getOrDefault(drink, 0) | customerBit);
}
}
// DP: dp[mask] = min drinks to satisfy customers in mask
int[] dp = new int[1 << n];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int mask = 0; mask < (1 << n); mask++) {
if (dp[mask] == Integer.MAX_VALUE) continue;
for (Map.Entry<Integer, Integer> entry : drinkMasks.entrySet()) {
int drinkMask = entry.getValue();
int newMask = mask | drinkMask;
dp[newMask] = Math.min(dp[newMask], dp[mask] + 1);
}
}
return dp[(1 << n) - 1];
}
private int greedySolution(Map<Integer, List<Integer>> preferences) {
// Greedy fallback implementation (same as Method 1)
Map<Integer, List<Integer>> drinkToCustomers = new HashMap<>();
Set<Integer> allCustomers = new HashSet<>();
for (Map.Entry<Integer, List<Integer>> entry : preferences.entrySet()) {
int customer = entry.getKey();
allCustomers.add(customer);
for (int drink : entry.getValue()) {
drinkToCustomers.computeIfAbsent(drink, k -> new ArrayList<>()).add(customer);
}
}
Set<Integer> unsatisfied = new HashSet<>(allCustomers);
int drinkCount = 0;
while (!unsatisfied.isEmpty()) {
int bestDrink = -1;
int maxCovered = 0;
for (Map.Entry<Integer, List<Integer>> entry : drinkToCustomers.entrySet()) {
int drink = entry.getKey();
List<Integer> customerList = entry.getValue();
int covered = 0;
for (int customer : customerList) {
if (unsatisfied.contains(customer)) covered++;
}
if (covered > maxCovered) {
maxCovered = covered;
bestDrink = drink;
}
}
if (bestDrink != -1) {
for (int customer : drinkToCustomers.get(bestDrink)) {
unsatisfied.remove(customer);
}
drinkCount++;
}
}
return drinkCount;
}
}
Python
class Solution:
def min_drinks(self, preferences: Dict[int, List[int]]) -> int:
if not preferences:
return 0
# Map customers to indices
customers = list(preferences.keys())
customer_to_index = {customer: i for i, customer in enumerate(customers)}
n = len(customers)
if n > 20:
return self._greedy_solution(preferences) # Fallback for large inputs
# Build drink masks
drink_masks = {}
for customer, drinks in preferences.items():
customer_bit = 1 << customer_to_index[customer]
for drink in drinks:
if drink not in drink_masks:
drink_masks[drink] = 0
drink_masks[drink] |= customer_bit
# DP: dp[mask] = min drinks to satisfy customers in mask
dp = [float('inf')] * (1 << n)
dp[0] = 0
for mask in range(1 << n):
if dp[mask] == float('inf'):
continue
for drink_mask in drink_masks.values():
new_mask = mask | drink_mask
dp[new_mask] = min(dp[new_mask], dp[mask] + 1)
return dp[(1 << n) - 1]
def _greedy_solution(self, preferences: Dict[int, List[int]]) -> int:
# Greedy fallback implementation (same as Method 1)
drink_to_customers = {}
all_customers = set(preferences.keys())
for customer, drinks in preferences.items():
for drink in drinks:
if drink not in drink_to_customers:
drink_to_customers[drink] = []
drink_to_customers[drink].append(customer)
unsatisfied = set(all_customers)
drink_count = 0
while unsatisfied:
best_drink = -1
max_covered = 0
for drink, customer_list in drink_to_customers.items():
covered = sum(1 for customer in customer_list if customer in unsatisfied)
if covered > max_covered:
max_covered = covered
best_drink = drink
if best_drink != -1:
for customer in drink_to_customers[best_drink]:
unsatisfied.discard(customer)
drink_count += 1
return drink_count
Complexity
- ⏰ Time complexity:
O(d * 2^n), where d is the number of unique drinks and n is the number of customers. We iterate through all possible customer subsets and try each drink - 🧺 Space complexity:
O(2^n), for the DP table storing minimum drinks for each customer subset