Looking for a mathematical solution to this small scheduling problem

Question

Say we have a list of rooms with their capacities and a list of meetings with the number of attendees. We want to match each meeting with one room in the following way:

1. A meeting can only be scheduled in a room with capacity equal to or greater than its attendance.
2. If surplus rooms are present, meetings should be scheduled so that the largest possible room is left unscheduled.
3. A meeting with a larger attendance should not be scheduled in a smaller room than a meeting with a smaller attendance.
4. Obviously we should find out if it is impossible to schedule the given meetings in the given rooms.

Can we arrive at the schedule efficiently? A single pass would be nice, some backtracking is ok, but the only option I can get to work (a rough algorithm plus dynamically shaking out violations of rule 3) is slower than I would like.

This question is not as easy as it looks! The naive linear approaches fail at least one criterion:

1. We can sort each list from high-to-low and start pairing the largest room to the largest session, we will come up with a solution any time it is possible, but we will have the smallest possible rooms left over rather than the largest. (Consider the case of 10 and 15-person meetings scheduled in 200, 30, and 20-person capacity rooms.)

2. We can sort the meeting list from high-to-low and then walk down it, trying to find the smallest room that is just large enough to contain this meeting. But sometimes this will result in a larger room being scheduled for a smaller meeting. (Consider scheduling 40 and 30-person meetings in 40 and 80-person rooms.)

But surely there is a better way to solve this relatively simple problem.

Answer 1

Can't you just sort both list from low to high and then put each meeting in the first (i.e. smallest) room that is large enough to hold it?

As far as I can see that meets all your criteria:

1. Check
2. This should follow directly from the fact that we always chose the smallest room possible
3. Since we've sorted the meeting from low attendance to high attendance, we'll never put a larger meeting in a smaller room.
4. If we reach the end of the room list before reaching the end of the meetings list, it wasn't possible to find a schedule.

Edit in response to your comment:

We make two passes. The first one goes above. After this, if there are any meetings left, proceed as follows:

Go through the list of rooms and the list of unscheduled meetings from highest to lowest.

If the current meeting fits in the current room: Put it in that room (adding the meeting that was previously in that room to the list of unscheduled meetings (at the lowest position, so that sort order is maintained)). Move to the next meeting and room in the list.

If the current meeting does not fit in the current room: This meeting can not be scheduled. Remove the meeting from the list and try the next meeting (with the same room).

Repeat until the list of unscheduled meetings is empty.