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

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!

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.