CareerCup

mix = { 'Cust1' : [ 'n3', 'n7', 'n5', 'n2' , 'n9' ],
        'Cust2' : [ 'n5' ],
        'Cust3' : [ 'n2' , 'n3' ],
        'Cust4' : [ 'n4' ],
        'Cust5' : [ 'n3' , 'n4' , 'n3' , 'n5' , 'n7' , 'n4' ] }
// what drinks serves who?
serving = fold( mix.keys , dict() ) as {
   values = mix[$.o]
   for ( v : values ){
     if ( v @ $.p ){
       $.p[v] += $.o 
     } else {
       $.p[v] = set($.o)
     }
   }
   $.p // return     
} 
// next, sort by no of customer a drink serves, and union off, 
// go with greedy mode. if adding a drink does not increase customer base
// no need to add it.. thus...
l = list ( serving ) as { [ $.key , $.value ] }
sortd(l) where { size($.left[1]) < size($.right[1])  }
drinks = set( l[0][0] )
catered = set( l[0][1] )
n = size(catered)
i = 1 
while ( n != size( mix ) ){ 
   catered |= l[i][1]
   if ( size(catered) > n ){
      n = size(catered) 
      drinks += l[i][0]
   }
   i += 1
}
println(drinks)
// caution, the problem is bin packing. Greedy is NOT a gurantee.
// en.wikipedia.org/wiki/Bin_packing_problem#Exact_algorithm
// A gurantee is, of course NP Hard.

class Solution
{
    static void Main(string[] args)
    {
        var pref = new Dictionary<int, List<int>>();
        pref.Add(0, new List<int>{0, 1, 3, 6});
        pref.Add(1, new List<int>{1, 4, 7});
        pref.Add(2, new List<int>{2, 4, 7, 5});
        pref.Add(3, new List<int>{3, 2 , 5});
        pref.Add(4, new List<int>{5, 8});
        
        int minDr = MinDrinks(pref);
        Console.WriteLine($"{minDr}");
    }
    
    public static int MinDrinks(Dictionary <int, List<int>> pref)
    {
        
        var map = new Dictionary<int, List<int>>();
        foreach( var key in pref.Keys)
        {
            var drink = pref[key];
            foreach( var d in drink)
            {
                if(!map.ContainsKey(d))
                {
                    map[d] = new List<int>();
                }
                map[d].Add(key);  //-> reverse map
            }
        }
        
        
        int drinkCount = 0;
        
        var peopleSet = new HashSet<int>();  // accounted folks
        
        while(peopleSet.Count < pref.Count()) // not all folks are acocunted
        {
            var key = GetMax(map, out bool isValid);
            if(!isValid)
            {
                return -1;
            }
            peopleSet.UnionWith(map[key]);
            drinkCount++;
            PruneMap(map, map[key]);
        }
        
        return drinkCount;
        
    }
    
    
    private static int GetMax(Dictionary<int, List<int>> map, out bool isValid)
    {
        int maxCount = 0;
        isValid = true;
        foreach( var k in map.Keys)
        {
            maxCount = map[k].Count > maxCount ? map[k].Count : maxCount;
        }
        
        if(maxCount == 0)
        {
            isValid = false;
        }
        
        return map.Where(c =>c.Value.Count() == maxCount).Select(c=> c.Key).First();
    }
    
    
    private static void PruneMap(Dictionary<int, List<int>> map, List<int> accounted)
    {
        foreach(var k in map.Keys.ToList())
        {
            map[k] = map[k].Except(accounted).ToList();
        }
    }
}

static void lazyBartender(){
		
		Set<Character> topLevelDrinksSet;
		Set<Character> topLevelCustomerSet;
		
//		Loop on drinks
		while(true){
			
			Set<Character> loopLevelCustomerSet;
			
//			Loop on customers
			while(true){
				
//				Does current customer have the current drink as a fav.
//				Yes -> loopLevelCustomerSet.add(Customer)
			}
			
//			If topLevelCustomerSet does NOT have all the counted customers
			if(!topLevelCustomerSet.containsAll(loopLevelCustomerSet)){
				topLevelCustomerSet.addAll(loopLevelCustomerSet);
				topLevelDrinksSet.add(currentDrink);
			}
		}
		
		System.out.println(topLevelDrinksSet);
	}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace test_aws
{
    class Bartender_drinks_distribution
    {
        public Bartender_drinks_distribution()
        {
            List<string> dr;
            Dictionary<string, List<string>> drinks = new Dictionary<string, List<string>>();
            Dictionary<string, List<string>> nlist = new Dictionary<string, List<string>>();
            nlist.Add("Cust1", new List<string>() { "n3", "n7", "n5", "n2", "n9" });
            nlist.Add("Cust2", new List<string>() { "n5" });
            nlist.Add("Cust3", new List<string>() { "n2", "n3" });
            nlist.Add("Cust4", new List<string>() { "n4" });
            nlist.Add("Cust5", new List<string>() { "n3", "n4", "n3", "n5", "n7", "n4" });

            foreach (KeyValuePair<string, List<string>> s in nlist)
            {
                foreach (string st in s.Value)
                {
                    if (!drinks.ContainsKey(st))
                    {
                        drinks.Add(st, new List<string>() { s.Key });
                    }
                    else
                    {
                        dr = drinks[st];
                        if (!dr.Contains(s.Key))
                            dr.Add(s.Key);
                    }

                }
            }
           IOrderedEnumerable< KeyValuePair < string,List<string>>> str =  drinks.OrderByDescending(t => t.Value.Count);
            int lencust = drinks.Count;
            List<string> finaldrinks = new List<string>();
            List<string> finalcust = new List<string>();

            foreach (KeyValuePair<string, List<string>> tt in str)
            {
                if (finalcust.Count >= lencust)
                    break;
                else
                {
                    if (!finaldrinks.Contains(tt.Key))
                    {
                        bool stat = false;
                        foreach(string tts in tt.Value)
                        {
                            if (!finalcust.Contains(tts))
                            {
                                finalcust.Add(tts);
                                stat = true;
                            }
                        }
                        if (stat)
                            finaldrinks.Add(tt.Key);
                    }
                }

            }
            Console.WriteLine(String.Join(",", finaldrinks.ToArray()));
            Console.WriteLine(String.Join(",",finalcust.ToArray()));

        }
    }
}

Time complexity of your solution is O(n3).

Here is my Algorithm,
1. Pick a customer
2. Iterate its drinks
3. check if any customer has this drinks if it has update cust with that drinks.
4. check which drinks have the most customer, and delete them from the set.
5. now for the rest customer go to point 1.

import java.util.*;

public class LazyBartender {

	public static void main(String[] args) {

		HashMap<String, Set<String>> custMap = new HashMap<String, Set<String>>();

		custMap.put("cust1", new HashSet<String>(Arrays.asList("n3", "n7", "n5", "n2", "n9")));
		custMap.put("cust2", new HashSet<String>(Arrays.asList("n5")));
		custMap.put("cust3", new HashSet<String>(Arrays.asList("n2", "n3")));
		custMap.put("cust4", new HashSet<String>(Arrays.asList("n4")));
		custMap.put("cust5", new HashSet<String>(Arrays.asList("n3", "n4", "n5", "n7")));

		System.out.println("total number of drinks required: " + countDrinks(custMap));
	}

	private static int countDrinks(HashMap custMap) {

		int count = 0;
		HashMap<String, ArrayList<String>> cutomerDrinksMap;
		Iterator custItr = custMap.entrySet().iterator();

		while (custItr.hasNext()) {
			Map.Entry pairs = (Map.Entry) custItr.next();

			String customer = (String) pairs.getKey();
			Set<String> drinksSet = (Set<String>) pairs.getValue();

			String maxDrinks = new String();
			int maxDrinksCount = 0;

			cutomerDrinksMap = new HashMap<String, ArrayList<String>>(); // temporaryMap

			for (String set : drinksSet) {

				
				cutomerDrinksMap.put(set, new ArrayList<>(Arrays.asList(customer)));
				
				if (cutomerDrinksMap.get(set).size() > maxDrinksCount) {
					maxDrinksCount = cutomerDrinksMap.get(set).size();
					maxDrinks = set;
				}
				
				
				Iterator internalCustItr = custMap.entrySet().iterator();
				while (internalCustItr.hasNext()) {

					Map.Entry internalPairs = (Map.Entry) internalCustItr.next();
					String internalCustomer = (String) internalPairs.getKey();

					if (!internalCustomer.equals(customer)) {

						Set<String> internalDrinksSet = (Set<String>) internalPairs.getValue();

						if (internalDrinksSet.contains(set)) {
							cutomerDrinksMap.get(set).add(internalCustomer);

							if (cutomerDrinksMap.get(set).size() > maxDrinksCount) {
								maxDrinksCount = cutomerDrinksMap.get(set).size();
								maxDrinks = set;
							}

						}

					}

				}

			}

			ArrayList customerList = cutomerDrinksMap.get(maxDrinks);
			
			if (customerList != null && customerList.size() > 0) {
				count++;
				for (int index = 0; index < customerList.size(); index++) {
					custMap.remove(customerList.get(index));
				}
			}
			custItr = custMap.entrySet().iterator();
		
		}

		return count;
	}

}

@NoOne hey, what programming language is that? I'm trying to understand the algorithm and what you're saying. If your solution is greedy then it might not be optimal, right? i.e. it might not yield the smallest set of drinks needed, but it gives a good enough solution.

Also how did you realize it was an instance of the Bin packing problem? I spent so long trying to think of a solution before realizing that I could only come up with inefficient or non-optimal algorithms; good thing you pointed it out.

create a node for all customers and drinks and then do a dfs starting from each customer...minimize the path having least drinks and all customers

using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography;
using System.Text;
using System.Threading.Tasks;
/*
 PROBLEM STATEMENT - Lazy Bartender :

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. A customer is satisfied if he gets atleast once of his favourite drink.
Example:
Cust1,n3,n7,n5,n2,n9
Cust2,n5
Cust3,n2,n3
Cust4,n4
Cust5,n3,n4,n6,n5,n7,n4

Output: 3(n3,n4,n5)
*/

namespace LazyBartender
{
    class Program
    {
        static void Main(string[] args)
        {
            List<Customer> customerList = ReadInput();
            Dictionary<string, int> dict = PrepareSortedDrinkDictionary(customerList);
            ServeCustomer(customerList, dict);
            Console.ReadKey();
        }

        private static void ServeCustomer(List<Customer> customerList, Dictionary<string, int> dict)
        {
            var minimumDrinkHashSet = new HashSet<string>();
            foreach (var element in dict)
            {
                foreach (var c in customerList)
                {
                    if (c.IsSatified == false && c.DrinkList.Contains(element.Key))
                    {
                        c.IsSatified = true;
                        minimumDrinkHashSet.Add(element.Key);
                        Console.WriteLine("Answer: " + c.CustomerId + " Drinks " + element.Key);
                    }

                    if (customerList.Any(x => x.IsSatified == false) == false)
                        break;
                }

                if (customerList.Any(x => x.IsSatified == false) == false)
                    break;
            }

            Console.WriteLine("Minimum drinks needed to serve all customers = " + minimumDrinkHashSet.Count);
        }

        private static Dictionary<string, int> PrepareSortedDrinkDictionary(List<Customer> customerList)
        {
            Dictionary<string, int> dict = new Dictionary<string, int>();
            foreach (var c in customerList)
            {
                foreach (var drink in c.DrinkList)
                {
                    if (dict.ContainsKey(drink))
                    {
                        dict[drink]++;
                    }
                    else dict.Add(drink, 1);
                }
            }

            dict = dict.OrderByDescending(x => x.Value).ToDictionary(x => x.Key, x => x.Value);

            return dict;
        }

        private static List<Customer> ReadInput()
        {
            List<Customer> list = new List<Customer>();
            string input = null;
            do
            {
                input = Console.ReadLine();
                if (string.IsNullOrEmpty(input) == false)
                {
                    var v = input.Split(',').ToList();
                    Customer c = new Customer { CustomerId = v[0] };
                    c.DrinkList.AddRange(v.GetRange(1, v.Count - 1));

                    list.Add(c);
                }

            } while (!string.IsNullOrEmpty(input));

            return list;
        }
    }

    class Customer
    {
        public string CustomerId { get; set; }
        public List<string> DrinkList = new List<string>();
        public bool IsSatified { get; set; }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography;
using System.Text;
using System.Threading.Tasks;
/*
 PROBLEM STATEMENT - Lazy Bartender :

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. A customer is satisfied if he gets atleast once of his favourite drink.
Example:
Cust1,n3,n7,n5,n2,n9
Cust2,n5
Cust3,n2,n3
Cust4,n4
Cust5,n3,n4,n6,n5,n7,n4

Output: 3(n3,n4,n5)
*/

namespace LazyBartender
{
    class Program
    {
        static void Main(string[] args)
        {
            List<Customer> customerList = ReadInput();
            Dictionary<string, int> dict = PrepareSortedDrinkDictionary(customerList);
            ServeCustomer(customerList, dict);
            Console.ReadKey();
        }

        private static void ServeCustomer(List<Customer> customerList, Dictionary<string, int> dict)
        {
            var minimumDrinkHashSet = new HashSet<string>();
            foreach (var element in dict)
            {
                foreach (var c in customerList)
                {
                    if (c.IsSatified == false && c.DrinkList.Contains(element.Key))
                    {
                        c.IsSatified = true;
                        minimumDrinkHashSet.Add(element.Key);
                        Console.WriteLine("Answer: " + c.CustomerId + " Drinks " + element.Key);
                    }

                    if (customerList.Any(x => x.IsSatified == false) == false)
                        break;
                }

                if (customerList.Any(x => x.IsSatified == false) == false)
                    break;
            }

            Console.WriteLine("Minimum drinks needed to serve all customers = " + minimumDrinkHashSet.Count);
        }

        private static Dictionary<string, int> PrepareSortedDrinkDictionary(List<Customer> customerList)
        {
            Dictionary<string, int> dict = new Dictionary<string, int>();
            foreach (var c in customerList)
            {
                foreach (var drink in c.DrinkList)
                {
                    if (dict.ContainsKey(drink))
                    {
                        dict[drink]++;
                    }
                    else dict.Add(drink, 1);
                }
            }

            dict = dict.OrderByDescending(x => x.Value).ToDictionary(x => x.Key, x => x.Value);

            return dict;
        }

        private static List<Customer> ReadInput()
        {
            List<Customer> list = new List<Customer>();
            string input = null;
            do
            {
                input = Console.ReadLine();
                if (string.IsNullOrEmpty(input) == false)
                {
                    var v = input.Split(',').ToList();
                    Customer c = new Customer { CustomerId = v[0] };
                    c.DrinkList.AddRange(v.GetRange(1, v.Count - 1));

                    list.Add(c);
                }

            } while (!string.IsNullOrEmpty(input));

            return list;
        }
    }

    class Customer
    {
        public string CustomerId { get; set; }
        public List<string> DrinkList = new List<string>();
        public bool IsSatified { get; set; }
    }
}

package awesome;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Set;

public class LazyBarTenderProblem {
static ArrayList<Integer> leastDrinksArray = new ArrayList<Integer>();
static HashMap<Integer, ArrayList<Character>> map2 = new HashMap<Integer, ArrayList<Character>>();
static HashMap<Integer, ArrayList<Character>> resultMap = new HashMap<Integer, ArrayList<Character>>();

private static void findLeastDrinksToBeSold(HashMap<Character, ArrayList<Integer>> map) {

HashMap<Integer, ArrayList<Character>> map1 = new HashMap<Integer, ArrayList<Character>>();

Set<Entry<Character, ArrayList<Integer>>> entrySet = map.entrySet();
for (Entry<Character, ArrayList<Integer>> entry : entrySet)
{
ArrayList<Integer> value = entry.getValue();
for (Integer integer : value)
{
ArrayList<Character> arrayList = map1.get(integer);
if (arrayList == null)
{
arrayList = new ArrayList<Character>();
}
arrayList.add(entry.getKey());
map1.put(integer, arrayList);
}
}
System.out.println(map1);
getMaxLenValues(map1);

System.out.println("The Least required number of Drinks required are:");
Set<Entry<Integer, ArrayList<Character>>> entrySet1 = resultMap.entrySet();
for (Entry<Integer, ArrayList<Character>> entry : entrySet1) // removal
{
if (!entry.getValue().isEmpty())
System.out.println(entry.getKey()+"="+entry.getValue());
}
}

private static HashMap<Integer, ArrayList<Character>> getMaxLenValues(HashMap<Integer, ArrayList<Character>> map1) {

while (!map1.isEmpty()) {
Integer drink = getMaxCustomer(map1);

ArrayList<Character> customers = map1.get(drink);
resultMap.put(drink, customers);
map1.remove(drink);

Set<Entry<Integer, ArrayList<Character>>> entrySet2 = map1.entrySet();

for (Entry<Integer, ArrayList<Character>> entry : entrySet2) // removal
{
ArrayList<Character> temCustomers = entry.getValue();
for (Character character : customers) {
if (temCustomers.contains(character)) {
temCustomers.remove(character);
}
}
}
}
return resultMap;
}

private static Integer getMaxCustomer(HashMap<Integer, ArrayList<Character>> map1) {
Integer drinkMax = 0;
Set<Entry<Integer, ArrayList<Character>>> entrySet = map1.entrySet();
for (Entry<Integer, ArrayList<Character>> entry : entrySet) {
if (drinkMax == 0) {
drinkMax = entry.getKey();
}
if (entry.getValue().size() > drinkMax) {
drinkMax = entry.getKey();
}
}
return drinkMax;
}

public static void main(String[] args) {
HashMap<Character, ArrayList<Integer>> map = new HashMap<Character, ArrayList<Integer>>();
ArrayList<Integer> choice1 = new ArrayList<Integer>();
choice1.add(1);
choice1.add(2);
choice1.add(3);
ArrayList<Integer> choice2 = new ArrayList<Integer>();
choice2.add(2);
choice2.add(4);
ArrayList<Integer> choice3 = new ArrayList<Integer>();
choice3.add(3);
// choice3.add(2);
choice3.add(4);
ArrayList<Integer> choice4 = new ArrayList<Integer>();
choice4.add(4);
choice4.add(5);
// choice4.add(5);
ArrayList<Integer> choice5 = new ArrayList<Integer>();
choice5.add(5);
choice5.add(6);
// choice5.add(4);
map.put('a', choice1);
map.put('b', choice2);
map.put('c', choice3);
map.put('d', choice4);
map.put('e', choice5);

findLeastDrinksToBeSold(map);
}

}

package awesome;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Set;

public class LazyBarTenderProblem {
	static ArrayList<Integer> leastDrinksArray = new ArrayList<Integer>();
	static HashMap<Integer, ArrayList<Character>> map2 = new HashMap<Integer, ArrayList<Character>>();
	static HashMap<Integer, ArrayList<Character>> resultMap = new HashMap<Integer, ArrayList<Character>>();

	private static void findLeastDrinksToBeSold(HashMap<Character, ArrayList<Integer>> map) {

		HashMap<Integer, ArrayList<Character>> map1 = new HashMap<Integer, ArrayList<Character>>();

		Set<Entry<Character, ArrayList<Integer>>> entrySet = map.entrySet();
		for (Entry<Character, ArrayList<Integer>> entry : entrySet)
		{
			ArrayList<Integer> value = entry.getValue();
			for (Integer integer : value) 
			{
				ArrayList<Character> arrayList = map1.get(integer);
				if (arrayList == null) 
				{
					arrayList = new ArrayList<Character>();
				}
				arrayList.add(entry.getKey());
				map1.put(integer, arrayList);
			}
		}
		System.out.println(map1);
		getMaxLenValues(map1);

		System.out.println("The Least required number of Drinks required are:");
		Set<Entry<Integer, ArrayList<Character>>> entrySet1 = resultMap.entrySet();
		for (Entry<Integer, ArrayList<Character>> entry : entrySet1) // removal
		{
			if (!entry.getValue().isEmpty())
				System.out.println(entry.getKey()+"="+entry.getValue());
		}
	}

	private static HashMap<Integer, ArrayList<Character>> getMaxLenValues(HashMap<Integer, ArrayList<Character>> map1) {

		while (!map1.isEmpty()) {
			Integer drink = getMaxCustomer(map1);

			ArrayList<Character> customers = map1.get(drink);
			resultMap.put(drink, customers);
			map1.remove(drink);

			Set<Entry<Integer, ArrayList<Character>>> entrySet2 = map1.entrySet();

			for (Entry<Integer, ArrayList<Character>> entry : entrySet2) // removal
			{
				ArrayList<Character> temCustomers = entry.getValue();
				for (Character character : customers) {
					if (temCustomers.contains(character)) {
						temCustomers.remove(character);
					}
				}
			}
		}
		return resultMap;
	}

	private static Integer getMaxCustomer(HashMap<Integer, ArrayList<Character>> map1) {
		Integer drinkMax = 0;
		Set<Entry<Integer, ArrayList<Character>>> entrySet = map1.entrySet();
		for (Entry<Integer, ArrayList<Character>> entry : entrySet) {
			if (drinkMax == 0) {
				drinkMax = entry.getKey();
			}
			if (entry.getValue().size() > drinkMax) {
				drinkMax = entry.getKey();
			}
		}
		return drinkMax;
	}

	public static void main(String[] args) {
		HashMap<Character, ArrayList<Integer>> map = new HashMap<Character, ArrayList<Integer>>();
		ArrayList<Integer> choice1 = new ArrayList<Integer>();
		choice1.add(1);
		choice1.add(2);
		choice1.add(3);
		ArrayList<Integer> choice2 = new ArrayList<Integer>();
		choice2.add(2);
		choice2.add(4);
		ArrayList<Integer> choice3 = new ArrayList<Integer>();
		choice3.add(3);
		// choice3.add(2);
		choice3.add(4);
		ArrayList<Integer> choice4 = new ArrayList<Integer>();
		choice4.add(4);
		choice4.add(5);
		// choice4.add(5);
		ArrayList<Integer> choice5 = new ArrayList<Integer>();
		choice5.add(5);
		choice5.add(6);
		// choice5.add(4);
		map.put('a', choice1);
		map.put('b', choice2);
		map.put('c', choice3);
		map.put('d', choice4);
		map.put('e', choice5);

		findLeastDrinksToBeSold(map);
	}

}

package awesome;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Set;

public class LazyBarTenderProblem{
	static ArrayList<Integer> leastDrinksArray = new ArrayList<Integer>();
	static HashMap<Integer, ArrayList<Character>> map2 = new HashMap<Integer, ArrayList<Character>>();
	static HashMap<Integer, ArrayList<Character>> resultMap = new HashMap<Integer, ArrayList<Character>>();

	private static void findLeastDrinksToBeSold(HashMap<Character, ArrayList<Integer>> map) {

		HashMap<Integer, ArrayList<Character>> map1 = new HashMap<Integer, ArrayList<Character>>();

		Set<Entry<Character, ArrayList<Integer>>> entrySet = map.entrySet();
		for (Entry<Character, ArrayList<Integer>> entry : entrySet)
		{
			ArrayList<Integer> value = entry.getValue();
			for (Integer integer : value) 
			{
				ArrayList<Character> arrayList = map1.get(integer);
				if (arrayList == null) 
				{
					arrayList = new ArrayList<Character>();
				}
				arrayList.add(entry.getKey());
				map1.put(integer, arrayList);
			}
		}
		System.out.println(map1);
		getMaxLenValues(map1);

		System.out.println("The Least required number of Drinks required are:");
		Set<Entry<Integer, ArrayList<Character>>> entrySet1 = resultMap.entrySet();
		for (Entry<Integer, ArrayList<Character>> entry : entrySet1) // removal
		{
			if (!entry.getValue().isEmpty())
				System.out.println(entry.getKey()+"="+entry.getValue());
		}
	}

	private static HashMap<Integer, ArrayList<Character>> getMaxLenValues(HashMap<Integer, ArrayList<Character>> map1) {

		while (!map1.isEmpty()) {
			Integer drink = getMaxCustomer(map1);

			ArrayList<Character> customers = map1.get(drink);
			resultMap.put(drink, customers);
			map1.remove(drink);

			Set<Entry<Integer, ArrayList<Character>>> entrySet2 = map1.entrySet();

			for (Entry<Integer, ArrayList<Character>> entry : entrySet2) // removal
			{
				ArrayList<Character> temCustomers = entry.getValue();
				for (Character character : customers) {
					if (temCustomers.contains(character)) {
						temCustomers.remove(character);
					}
				}
			}
		}
		return resultMap;
	}

	private static Integer getMaxCustomer(HashMap<Integer, ArrayList<Character>> map1) {
		Integer drinkMax = 0;
		Set<Entry<Integer, ArrayList<Character>>> entrySet = map1.entrySet();
		for (Entry<Integer, ArrayList<Character>> entry : entrySet) {
			if (drinkMax == 0) {
				drinkMax = entry.getKey();
			}
			if (entry.getValue().size() > drinkMax) {
				drinkMax = entry.getKey();
			}
		}
		return drinkMax;
	}

	public static void main(String[] args) {
		HashMap<Character, ArrayList<Integer>> map = new HashMap<Character, ArrayList<Integer>>();
		ArrayList<Integer> choice1 = new ArrayList<Integer>();
		choice1.add(1);
		choice1.add(2);
		choice1.add(3);
		ArrayList<Integer> choice2 = new ArrayList<Integer>();
		choice2.add(2);
		choice2.add(4);
		ArrayList<Integer> choice3 = new ArrayList<Integer>();
		choice3.add(3);
		// choice3.add(2);
		choice3.add(4);
		ArrayList<Integer> choice4 = new ArrayList<Integer>();
		choice4.add(4);
		choice4.add(5);
		// choice4.add(5);
		ArrayList<Integer> choice5 = new ArrayList<Integer>();
		choice5.add(5);
		choice5.add(6);
		// choice5.add(4);
		map.put('a', choice1);
		map.put('b', choice2);
		map.put('c', choice3);
		map.put('d', choice4);
		map.put('e', choice5);

		findLeastDrinksToBeSold(map);
	}

}

public class LazyBartender {

	static private final java.util.HashMap<String, DrinkCustomerBase> drinksCustomerBase =new java.util.HashMap<>();
	
	static private final Customer customers[] = { 
			new Customer("C1", new String[] { "n3", "n7", "n5", "n2", "n9" }),
			new Customer("C2", new String[] { "n5" }), 
			new Customer("C3", new String[] { "n2", "n3" }),
			new Customer("C4", new String[] { "n4" }),
			new Customer("C5", new String[] { "n3", "n4", "n5", "n7" }) };


	/*
	 * Helper class Customer
	 */
	public static class Customer {
		public final String name;
		public final java.util.HashSet<String> drinks = new java.util.HashSet<String>();

		Customer(String name, String[] drinks) {
			this.name = name;
			this.drinks.addAll(java.util.Arrays.asList(drinks) );
			for (String d:drinks) {
				DrinkCustomerBase dc = drinksCustomerBase.get(d);
				if (dc == null){
					dc = new DrinkCustomerBase(d);
					drinksCustomerBase.put(d, dc);
				}
				dc.customers.add(this);
			}
		}
		boolean hasDrink(String d) {
			return drinks.contains(d);
		}
	}

	/*
	 * Helper class DrinkCustomerBase: drink to customers relation
	 */
	public static class DrinkCustomerBase implements Comparable<DrinkCustomerBase> {
		public final String drink;
		public final java.util.HashSet<Customer> customers;

		public DrinkCustomerBase(String drink) {
			this.drink = drink;
			this.customers = new java.util.HashSet<Customer> ();
		}

		// compare by customer base, greater base first 
		@Override
		public int compareTo(DrinkCustomerBase dc) {
			return dc.customers.size() - this.customers.size();
		}
	}

	/*
	 * Brute-force combination n Choose k, k: 1..n, n: total number of unique drinks    
	 */
	static boolean checkCustomers(String drinks[]) {
		java.util.HashSet<Customer> customersSet = new java.util.HashSet<Customer>();
		for (Customer c: customers) {
			for (String d:drinks){
				if (c.hasDrink(d)){
					customersSet.add(c);
					if (customersSet.size() == customers.length)
						return true;
				}
			}			
		}
		return false;
	}

	/*
	 * n choose k
	 */
	static boolean drinksFound = false;
	static <T> void combinations(T arr[], T data[], int start, int end, int index, int r) {
		if (index == r) {
			if (!drinksFound && checkCustomers ((String[])data) ){				
				System.out.println(java.util.Arrays.asList(data));
				drinksFound = true;
			}
			return;
		}

		for (int i = start; i <= end && end - i + 1 >= r - index; i++) {
			data[index] = arr[i];
			combinations(arr, data, i + 1, end, index + 1, r);
		}
	}
	
	/*
	 * BF. find first smallest set
	 */
	static void findDrinksBf () {
		
		String[] uniquedrinks = drinksCustomerBase.keySet().toArray(new String[0]);
		/*
		 * check combinations n:i
		 */
		for (int i = 1; i <= uniquedrinks.length; ++i){
	        String data[]=new String[i];
	        combinations(uniquedrinks, data, 0, uniquedrinks.length -1, 0, i);
	        if (drinksFound)
	        	break;
		}			
	}

	/*
	 * Find good enough for the lazy
	 */
	static void findGoodDrinkSet() {
		java.util.LinkedList<DrinkCustomerBase> drinkList = new java.util.LinkedList<>(drinksCustomerBase.values());
		drinkList.sort(null); // sort using DrinkCustomerBase.compareTo 
		
		java.util.HashSet<Customer> customerBase = new java.util.HashSet<>();
		java.util.HashSet<String> drinks = new java.util.HashSet<>();

		for (DrinkCustomerBase dc : drinkList) {
			for (Customer c : dc.customers) {
				if (!customerBase.contains(c)) {
					drinks.add(dc.drink);
					customerBase.add(c);
				}
			}
		}
		System.out.println(drinks.toString());		
	}
	
	public static void main(String[] arg) {
		findGoodDrinkSet();
		findDrinksBf();
	}

}

class Customer
		{
			public string CustomerId { get; set; }
			public List<string> DrinkList = new List<string>();
		}
		 
		static void Main(string[] args)
		{
			List<Customer> customers = new List<Customer>
			{
				new Customer() {CustomerId = "Cust1", DrinkList = {"n3", "n7", "n5", "n2", "n9"}},
				new Customer() {CustomerId = "Cust2", DrinkList = {"n5"}},
				new Customer() {CustomerId = "Cust3", DrinkList = {"n2", "n3"}},
				new Customer() {CustomerId = "Cust4", DrinkList = {"n4"}},
				new Customer() {CustomerId = "Cust5", DrinkList = {"n3", "n4", "n3", "n5", "n7", "n4"}},
			};
			Dictionary<string, string> mandatory = new Dictionary<string, string>();
			string validDrinks=String.Empty;
			List<string> allDrinks = new List<string>();
			for (int i =0; i < customers.Count; i++)
			{
				var cust = customers[i];
				if (cust.DrinkList.Count == 1)
				{
					mandatory.Add(cust.DrinkList[0],cust.CustomerId);
					validDrinks = validDrinks + cust.DrinkList[0] + ",";
				}
				else
				{
					foreach (var drink in cust.DrinkList)
					{
						if (mandatory.ContainsKey(drink))
						{
							continue;
						}
						bool isUnique = false;
						bool isCommon = false;
						List<string> common = new List<string>();
						List<string> Unique = new List<string>();
						for (int j = i + 1; j < customers.Count; j++)
						{
							var next = customers[j];
							if (next.DrinkList.Count > 1)
							{
								isUnique = !next.DrinkList.Contains(drink);
								isCommon = (next.DrinkList.Contains(drink));
								if (isCommon && !common.Contains(drink))
								{
									common.Add(drink);
								}
								if (isUnique && !Unique.Contains(drink))
								{
									Unique.Add(drink);
								}
								if (isUnique && common.Contains(drink))
								{
									common.Remove(drink);
									isUnique = false;
									isCommon = false;
								}
								if(isCommon && Unique.Contains(drink))
								{
									Unique.Remove(drink);
									isCommon = false;
									isUnique = false;
								}
							}
						}
						if (!allDrinks.Contains(drink))
						{
							allDrinks.Add(drink);
						}
						if ((isUnique && !mandatory.ContainsValue(cust.CustomerId)) && !allDrinks.Contains(drink) || (isCommon && !mandatory.ContainsKey(drink)))
						{
							mandatory.Add(drink, cust.CustomerId);
							validDrinks = validDrinks + drink + ",";
						}
					}
					
				}
				
			}
			Console.Write(string.Format("{0}({1})", mandatory.Count, validDrinks.TrimEnd(',')));
			Console.ReadKey();
		}

/**

Algorithm:
C -> NumberOfCustomers
N -> Max Number of Drinks
1. Create a Sort Order Matrix based on the frequencies O(C * N)
2. Sort each customer's favorites based on the Sort order matrix O(C * NlogN)
3. Add first elements of each to the set. O(C)
4. return the max of 1, size of set. O(1)

Also, handles a case where no customer/ some customers has any favorites.

All Values should start with 0.

*/


import java.util.*;
public class Solution {
	public int minDrinksToPrepare(int numberOfDrinks, int numberOfCustomers, ArrayList<Integer>[] favorites) {
		if(numberOfDrinks <= 1) {
			return Math.max(numberOfDrinks, 0);
		}

		HashSet<Integer> result = new HashSet<Integer>();
		int[] sortOrder = getSortOrder(favorites, numberOfDrinks);

		sortBasedOnOrder(favorites, sortOrder);

		getFirstElementsOfAll(favorites, result);

		return Math.max(1, result.size());
	}
	
	private void sortBasedOnOrder(ArrayList<Integer>[] favorites, int[] sortOrder) {
		for(int i = 0; i < favorites.length; i++) {
			Collections.sort(favorites[i], new OrderedSortComparator(sortOrder));
		}
	}
	
	class OrderedSortComparator implements Comparator<Integer> {
		int[] order;
		// We can also bring make this map as outer class variable and use the same instance,
		// instead of creating a new one everytime
		HashMap<Integer, Integer> map;
	
		OrderedSortComparator(int[] order) {
			this.order = order;
			map = new HashMap<Integer, Integer>();
			for(int i = 0; i < order.length; i++) {
				if(!map.containsKey(order[i])) {
					map.put(order[i], i);
				}
			}
		}
	
		public int compare(Integer a, Integer b) {
			if(!map.containsKey(a) && !map.containsKey(b)) {
				return (a > b) ? b : a;
			} else if(!map.containsKey(a)) {
				return b;
			} else if(!map.containsKey(b)) {
				return a;
			} else {
				return (map.get(a) <= map.get(b)) ? a : b;
			}
		}
	}
	
	private void getFirstElementsOfAll(ArrayList<Integer>[] favorites, HashSet<Integer> result) {
		for(int i = 0; i < favorites.length; i++) {
			for(int fav : favorites[i]) {
				result.add(fav);
				break;
			}
		}
	}
	
	private int[] getSortOrder(ArrayList<Integer>[] favorites, int numberOfDrinks) {
		int[] sortOrder = new int[numberOfDrinks];
		for(int i = 0; i < favorites.length; i++) {
			sortOrder[i] = 0;
		}
		
		for(int i = 0; i < favorites.length; i++) {
			for(int j : favorites[i]) {
				sortOrder[j]++;
			}
		}
		return sortOrder;
	}
}

Overall Time Complexity : O(C * NlogN)

The problem above is an instance of Hitting Set (Derivation of Set Cover) Problem which is an NP-Complete problem.

import java.util.*;

public class LazyBartender {

	public static void main(String[] args) {

		HashMap<String, Set<String>> custMap = new HashMap<String, Set<String>>();

		custMap.put("cust1", new HashSet<String>(Arrays.asList("n3", "n7", "n5", "n2", "n9")));
		custMap.put("cust2", new HashSet<String>(Arrays.asList("n5")));
		custMap.put("cust3", new HashSet<String>(Arrays.asList("n2", "n3")));
		custMap.put("cust4", new HashSet<String>(Arrays.asList("n4")));
		custMap.put("cust5", new HashSet<String>(Arrays.asList("n3", "n4", "n5", "n7")));

		System.out.println("total number of drinks required: " + countDrinks(custMap));
	}

	private static int countDrinks(HashMap custMap) {
		int count =0;
		HashMap<String, Set<String>> drinksMap = new HashMap<String, Set<String>>();
		HashMap<String,Integer> drinksvscustcount = new HashMap<String, Integer>();
		Iterator custvsdrinksIt = custMap.keySet().iterator();
		//Prepare drink map
		while(custvsdrinksIt.hasNext()){
			String customer = (String) custvsdrinksIt.next();
			Set<String> drinks = (Set<String>) custMap.get(customer);
			for (String drink : drinks) {
				if(drinksMap.containsKey(drink)){
					drinksMap.get(drink).add(customer);
				}else{
					Set<String> custs = new HashSet<String>();
					custs.add(customer);
					drinksMap.put(drink, custs);
				}
				drinksvscustcount.put(drink, drinksMap.get(drink).size());
			}
		}	
		Set<String> finalDrinks = new HashSet<String>();
		Set<String> finalCusts = new HashSet<String>();
		while(finalCusts.size() < custMap.size()){
			String drink = getDrinkWithMaxCustomers(drinksvscustcount);
			Set<String> custs = drinksMap.get(drink);
			for(String cust : custs){
				if(finalCusts.contains(cust)){
					continue;
				}else{
					finalDrinks.add(drink);
					finalCusts.add(cust);
				}
			}
			drinksvscustcount.remove(drink);
		}
		System.out.println("finalDrinks"+finalDrinks);
		return finalDrinks.size();
	}

	public static String getDrinkWithMaxCustomers(HashMap<String, Integer> drinksvscustcount){
		int maxCustomersForADrink = 0;
		String maxDrink = "";
		Set<String> drinks = drinksvscustcount.keySet();
		for(String drink : drinks){
			if(drinksvscustcount.get(drink) > maxCustomersForADrink){
				maxCustomersForADrink = drinksvscustcount.get(drink);
				maxDrink = drink;
			}
		}
		return maxDrink;
	}
}

# The method to find the least number of drinks

def least_drinks_serve_all(drink_schedule, drinks, customers)
	array_for_elimination = Array.new(drinks){Array.new(customers + 1, 0)}
	# Now making the array for elimination process
	array_for_elimination.each_with_index do |row, i|
		row.each_with_index do |col, j|
			next unless drink_schedule[i] && drink_schedule[i][j]
			index_of_drink = drink_schedule[i][j]
			array_for_elimination[index_of_drink][i] = 1
		end
	end
	# adding the total preference of each drink as last column
	array_for_elimination.each_with_index do |row, i|
		sum = 0
		row.each_with_index do |col, j|
			sum += array_for_elimination[i][j]
		end
		array_for_elimination[i][customers] = sum
	end
	customers_left = customers # counter for tracking the number of customers left to be served
	least_drink_count = 0 # counter for least number of drinks to be served by the lazy tenderer
	while customers_left > 0
		index_to_eliminate = 0
		row_max_val = 0
		# loop through to find the row index with maximum sum
		array_for_elimination.each_with_index do |row, i|
			if array_for_elimination[i][customers] > row_max_val
				row_max_val = array_for_elimination[i][customers]
				index_to_eliminate = i
			end
		end
			least_drink_count += 1 # we found one drink that serves maximum customers at the end of 1 iteration
			customers_left -= row_max_val # we have served to row_max_val customers
			# for to eliminate the counted drink with its customers
			for i in 0..customers
				if array_for_elimination[index_to_eliminate][i] == 1
					array_for_elimination.each_with_index do |row, j|
						if array_for_elimination[j][i] == 1
							array_for_elimination[j][i] = 0
							array_for_elimination[j][customers] -= 1
						end
					end
				end
			end
		end
	return least_drink_count
end

# The method to find the least number of drinks

def least_drinks_serve_all(drink_schedule, drinks, customers)
array_for_elimination = Array.new(drinks){Array.new(customers + 1, 0)}
# Now making the array for elimination process
array_for_elimination.each_with_index do |row, i|
row.each_with_index do |col, j|
next unless drink_schedule[i] && drink_schedule[i][j]
index_of_drink = drink_schedule[i][j]
array_for_elimination[index_of_drink][i] = 1
end
end
# adding the total preference of each drink as last column
array_for_elimination.each_with_index do |row, i|
sum = 0
row.each_with_index do |col, j|
sum += array_for_elimination[i][j]
end
array_for_elimination[i][customers] = sum
end
customers_left = customers # counter for tracking the number of customers left to be served
least_drink_count = 0 # counter for least number of drinks to be served by the lazy tenderer
while customers_left > 0
index_to_eliminate = 0
row_max_val = 0
# loop through to find the row index with maximum sum
array_for_elimination.each_with_index do |row, i|
if array_for_elimination[i][customers] > row_max_val
row_max_val = array_for_elimination[i][customers]
index_to_eliminate = i
end
end
least_drink_count += 1 # we found one drink that serves maximum customers at the end of 1 iteration
customers_left -= row_max_val # we have served to row_max_val customers
# for to eliminate the counted drink with its customers
for i in 0..customers
if array_for_elimination[index_to_eliminate][i] == 1
array_for_elimination.each_with_index do |row, j|
if array_for_elimination[j][i] == 1
array_for_elimination[j][i] = 0
array_for_elimination[j][customers] -= 1
end
end
end
end
end
return least_drink_count
end

```
# Lazy Bar tenderer code
# A bar has m type of drinks and has n customers having
# their personal preference of drinks known
# This is represented by a 2D array represented
# as the rows represent each customer and columns as their preferred drinks type
# We have a lazy bar tenderer who would like to make(or even learn) the least number of
# drinks so as to serve the customers their choice of drinks
# we have the array, m the number of drink types, and n the number of customers as the input
# we as supposed to give the least count of drinks the bar tenderer needs to make as 'count'
#
# Sample input

array = [
[0, 1, 3, 6],
[1, 4, 7],
[2, 4, 7, 5],
[3, 2, 5],
[5, 8]
]

n = 5
m = 9

# Sample output should be count = 2 (the drink number 5 and 1)
#

# We will make an array of m rows each representing the drink type number
# and n+1 columns where n columns are for customers with preference represented as
# binary value either 0 or 1
# and the +1 column for the sum of preferences for each drink row
#
# The arr for sample input is
#
# 0 1 2 3 4 Sum
#
# 0 1 0 0 0 0 1
# 1 1 1 0 0 0 2
# 2 0 0 1 1 0 2
# 3 1 0 0 1 0 2
# 4 0 1 1 0 0 2
# 5 0 0 1 1 1 3
# 6 1 0 0 0 0 1
# 7 0 1 1 0 0 2
# 8 0 0 0 0 1 1
#
# We will find the max value of sum ie the most preferred drink, so naturally the bar tenderer
# needs to know how to make it
# So we can eliminate the drink with the customers whom we can serve with the drink
# Now just increment the count variable count++
# and shortlist the array as below
#
# 0 1 Sum
#
# 0 1 0 1
# 1 1 1 2
# 2 0 0 0
# 3 1 0 1
# 4 0 1 1
# 6 1 0 1
# 7 0 1 1
# 8 0 0 0
#
# Now you may need to select the drink with maxim preference and
# go on...until all of the customers are served
# ie, till the array is empty or customers left is zero
# For the example thats it ... all are served with the two drinks, drinks 5 and 1
# Now lets go to the codes for that....
#
# The method to find the least number of drinks

def least_drinks_serve_all(drink_schedule, drinks, customers)
array_for_elimination = Array.new(drinks){Array.new(customers + 1, 0)}
# Now making the array for elimination process
array_for_elimination.each_with_index do |row, i|
row.each_with_index do |col, j|
next unless drink_schedule[i] && drink_schedule[i][j]
index_of_drink = drink_schedule[i][j]
array_for_elimination[index_of_drink][i] = 1
end
end
# adding the total preference of each drink as last column
array_for_elimination.each_with_index do |row, i|
sum = 0
row.each_with_index do |col, j|
sum += array_for_elimination[i][j]
end
array_for_elimination[i][customers] = sum
end
customers_left = customers # counter for tracking the number of customers left to be served
least_drink_count = 0 # counter for least number of drinks to be served by the lazy tenderer
while customers_left > 0
index_to_eliminate = 0
row_max_val = 0
# loop through to find the row index with maximum sum
array_for_elimination.each_with_index do |row, i|
if array_for_elimination[i][customers] > row_max_val
row_max_val = array_for_elimination[i][customers]
index_to_eliminate = i
end
end
least_drink_count += 1 # we found one drink that serves maximum customers at the end of 1 iteration
customers_left -= row_max_val # we have served to row_max_val customers
# for to eliminate the counted drink with its customers
for i in 0..customers
if array_for_elimination[index_to_eliminate][i] == 1
array_for_elimination.each_with_index do |row, j|
if array_for_elimination[j][i] == 1
array_for_elimination[j][i] = 0
array_for_elimination[j][customers] -= 1
end
end
end
end
end
return least_drink_count
end
```

# Lazy Bar tenderer code
# A bar has m type of drinks and has n customers having
# their personal preference of drinks known
# This is represented by a 2D array represented
# as the rows represent each customer and columns as their preferred drinks type
# We have a lazy bar tenderer who would like to make(or even learn) the least number of
# drinks so as to serve the customers their choice of drinks
# we have the array, m the number of drink types, and n the number of customers as the input
# we as supposed to give the least count of drinks the bar tenderer needs to make as 'count'
#
# Sample input

array = [
[0, 1, 3, 6],
[1, 4, 7],
[2, 4, 7, 5],
[3, 2, 5],
[5, 8]
]

n = 5
m = 9

# Sample output should be count = 2 (the drink number 5 and 1)
#

# We will make an array of m rows each representing the drink type number
# and n+1 columns where n columns are for customers with preference represented as
# binary value either 0 or 1
# and the +1 column for the sum of preferences for each drink row
#
# The arr for sample input is
#
# 		0	1	2	3	4	Sum
#
# 0		1	0	0	0	0	1
# 1		1	1	0	0	0	2
# 2		0	0	1	1	0	2
# 3		1	0	0	1	0	2
# 4		0	1	1	0	0	2
# 5		0	0	1	1	1	3
# 6		1	0	0	0	0	1
# 7		0	1	1	0	0	2
# 8		0	0	0	0	1	1
#
# We will find the max value of sum ie the most preferred drink, so naturally the bar tenderer
# needs to know how to make it
# So we can eliminate the drink with the customers whom we can serve with the drink
# Now just increment the count variable count++
# and shortlist the array as below
#
# 		0	1	Sum
#
# 0		1	0	1
# 1		1	1	2
# 2		0	0	0
# 3		1	0	1
# 4		0	1	1
# 6		1	0	1
# 7		0	1	1
# 8		0	0	0
#
# Now you may need to select the drink with maxim preference and
# go on...until all of the customers are served
# ie, till the array is empty or customers left is zero
# For the example thats it ... all are served with the two drinks, drinks 5 and 1
# Now lets go to the codes for that....
#
# The method to find the least number of drinks

def least_drinks_serve_all(drink_schedule, drinks, customers)
	array_for_elimination = Array.new(drinks){Array.new(customers + 1, 0)}
	# Now making the array for elimination process
	array_for_elimination.each_with_index do |row, i|
		row.each_with_index do |col, j|
			next unless drink_schedule[i] && drink_schedule[i][j]
			index_of_drink = drink_schedule[i][j]
			array_for_elimination[index_of_drink][i] = 1
		end
	end
	# adding the total preference of each drink as last column
	array_for_elimination.each_with_index do |row, i|
		sum = 0
		row.each_with_index do |col, j|
			sum += array_for_elimination[i][j]
		end
		array_for_elimination[i][customers] = sum
	end
	customers_left = customers # counter for tracking the number of customers left to be served
	least_drink_count = 0 # counter for least number of drinks to be served by the lazy tenderer
	while customers_left > 0
		index_to_eliminate = 0
		row_max_val = 0
		# loop through to find the row index with maximum sum
		array_for_elimination.each_with_index do |row, i|
			if array_for_elimination[i][customers] > row_max_val
				row_max_val = array_for_elimination[i][customers]
				index_to_eliminate = i
			end
		end
			least_drink_count += 1 # we found one drink that serves maximum customers at the end of 1 iteration
			customers_left -= row_max_val # we have served to row_max_val customers
			# for to eliminate the counted drink with its customers
			for i in 0..customers
				if array_for_elimination[index_to_eliminate][i] == 1
					array_for_elimination.each_with_index do |row, j|
						if array_for_elimination[j][i] == 1
							array_for_elimination[j][i] = 0
							array_for_elimination[j][customers] -= 1
						end
					end
				end
			end
		end
	return least_drink_count
end