寻找一个数学解决这个小调度问题

假设我们有一个会议室列表和与会者人数列表。我们希望通过以下方式将每个会议与一个房间相匹配:

1. 会议只能安排在容量等于或大于出席人数的会议室中。
2. 如果有多余的房间,则应安排会议,以便最大可能的房间没有安排。
3. 出席人数较多的会议不应安排在比出席人数较少的会议更小的会议室。
4. 显然,我们应该弄清楚是否不可能在指定的房间里安排指定的会议。

我们能有效地到达时间表吗?一次通过就好了,一些回溯是可以的,但是我唯一能开始工作的选择(一个粗略的算法加上动态摆脱违反规则3的行为)比我想要的要慢。

这个问题不像看上去那么容易!天真的线性方法至少有一个标准失败:

1. 我们可以将每个列表从高到低排序,并开始将最大的房间与最大的会话配对,我们将在任何可能的时候提出解决方案,但我们将保留尽可能小的房间,而不是最大的房间(考虑在200人、30人和20人会议室安排10人和15人会议的情况。)

2. 我们可以把会议清单从高到低排序,然后沿着它往下走,试着找到一个最小的房间,刚好可以容纳这个会议。但有时这会导致一个更大的房间被安排在一个更小的会议(考虑在40人和80人的会议室安排40人和30人的会议。)