ruby - Looking for a mathematical solution to this small scheduling problem -

Say we have a list of rooms with our capacity and there is a list of meetings with the number of attendees. We want to match each meeting to a room in the following room:

1. A meeting can only be set in the room with its capacity or equivalent capacity.
2. If surplus rooms are present, then meetings should be determined so that the largest possible room has been left unspecified.
3. The large presence should not be fixed in a small room compared to the meeting with a small presence.
4. Obviously we should know that it is impossible to schedule the given meetings in the given room.

Can we reach efficiently from time to time? A single pass would be fine, some back lyaking is fine, but the only option I can slow down (a thick algorithm plus dynamic dynamically violating rule 3) is what I want.

This question seems to be not as easy as it is! Simple linear approaches are unsuccessful in at least one criterion:

1. We can sort each list on high-to-high and start adding the largest room to the largest session It can be possible, at any time, it is possible to have a solution, but we will be left most in the smallest possible rooms. (Consider the case of fixed 10 and 15 person meetings in rooms with 200, 30, and 20-person capacity.)

2. We have the meeting list high-to-low and Then running it down, trying to find just such a big room to include this meeting. But sometimes it is being set for a small meeting for a small room. (Consider 40 and 30-person meetings in 40 and 80-person rooms.)

But of course, to solve this relatively simple problem There is a better way of

You can not list both the lists to the least, and then each meeting first (smallest)

1. Check it
2. It should follow directly
3. Since we have a meeting in high presence with less presence, so we have a large meeting anytime in a small room will not do.
4. If we reach the end of the list of rooms before reaching the end of the list of meetings, then it was not possible to find a time.

Edit in response to your comment:

We make two passes. First one goes up, after this, if any meeting is left out, then proceed as follows:

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

If the current meeting fits in the current room: keep it in that room (before adding the meeting that was in the list of unscheduled meetings in that room (in the lowest case, so that the order kept maintained Have been done)). Go to the next meeting and room in the list.

If the present meeting is not fit in the current room: this meeting can not be determined. Remove the meeting from the list and try the next meeting (in the same room).

Repeat the list of unscheduled meetings until empty.