Efficient algorithm for creating an ideal distribution of groups into containers with potential overflow?

Question

I have groups of students that need to be allocated into classrooms of a fixed capacity (say, 100 chairs in each).

Each group must only be allocated to a single classroom, even if it is larger than the capacity (ie there can be an overflow, with students standing up)

I need an algorithm to make the allocations with minimum overflows and under-capacity classrooms.

A naive algorithm to do this allocation is horrendously slow when having ~200 groups, with a distribution of about half of them being under 20% of the classroom size.

Any ideas where I can find at least some good starting point for making this algorithm lightning fast?

Thanks!

Answer 1

This is similar to the bin packing problem, which is NP complete. It is difficult to find a fast optimal algorithm but it is possible to find a fast nearly optimal algorithm. You can start by using a greedy approach - placing the largest groups first and putting them into the smallest gap they fit in.