UVa 10249

From Algorithmist
Jump to: navigation, search

10249 - The Grand Dinner[edit]

Summary[edit]

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.

Explanation[edit]

  • 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.


Gotchas[edit]

  • 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.


Implementations[edit]

  • My Implementation in Java[1]

Input[edit]

4 5
4 5 3 5
3 5 2 6 4
4 5
4 5 3 5
3 5 2 6 3
0 0

Output[edit]

1
1 2 4 5
1 2 3 4 5
2 4 5
1 2 3 4 5
0