10249 - The Grand Dinner
Given a list of tables with capacity of each and list of teams with number of members in each, You are asked to output a seating arrangement(not unique) such that no two members of the same team sit at the same table. If no such arrangement is possible then output 0.
- We can solve this problem with Greedy approach.
- First we need to have a structure/class for table to store table number(will need to tell in case of valid solution) as well as capacity.
- Maintain two arrays of teams(containing number of memberss in ith team) and for tables.
- Now sort the tables in decreasing order of their capacity.
- For each member of every team greedily choose the table with maximum capacity and assign it to the member, and reduce its capacity by one.
- If maximum team size > number of tables, then we can say that no solution is possible without any of the above calculations.(Pigeonhole principle.)
- If in the above process, capacity of a table becomes less than zero, then no valid arrangement is possible.
- My Implementation in Java
4 5 4 5 3 5 3 5 2 6 4 4 5 4 5 3 5 3 5 2 6 3 0 0
1 1 2 4 5 1 2 3 4 5 2 4 5 1 2 3 4 5 0