# UVa 10249

Jump to navigation
Jump to search

## Contents

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