# UVa 10249

Jump to navigation Jump to search

## Summary

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

• 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

• 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

• My Implementation in Java[1]

```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
```