Greedy Maximum Flow

The Dining Problem:
Several families go out to dinner together. In order to increase their social interaction, they would like to sit at tables so that no two members of the same family are at the same table. Assume that the dinner contingent has p families and that the ith family has a(i) members. Also, assume there are q tables available and that the jth table has a seating capacity of b(j).

The question is: What is the maximum number of persons we can sit on the tables?

EDIT: This problem can be solved creating a Graph and running a maximum flow algorithm. But if we have 2*10^3 vertices with Dinic algorithm, the global complexity is O(10^6*10^6) = O(10^12).

If we only sit always the larger groups first, in a greedy manner. The complexity is O(10^6).

So my questions are:

1) Does the greedy approach in this problem work?

2) What is the best algorithm to solve this problem?

Solution

It is easy to come up with examples where such seating is simply impossible, so here's a pseudo code for solving the problem assuming that the problem is solvable:

Sort each family i by a(i) in decreasing order
Add each table j to a max-heap with b(j) as the key

For each family i from the sorted list:
    Pop a(i) tables from max-heap
    Add one member of i to each table
    Add each table j back into the max-heap with b(j) = b(j) - 1

Let n = a(1) + a(2) + ... + a(p) (i.e. total number of people)

Assuming a binary heap is used for the max-heap, the time complexities are:

Sorting families: O(plog(p))
Initializing max-heap of tables: O(qlog(q))
All pops and pushes to/from max-heap: O(nlog(q))

Giving the total time complexity of O(plog(p) + qlog(q) + nlog(q)), where O(nlog(q)) will likely dominate.

Since we are dealing with integers, if we use a 1D bucket system for the max-heap such that c is the maximum b(j), then we will end up with just O(n + c) (assuming the max-heap operations dominate), which maybe quicker.

Finally, please up-vote David's answer as the proof was required and is awesome.