调度贪婪的选择p‌r‌o‌b‌l‌e‌m

Question

我有一个有趣的问题要用贪婪的选择来解决。

给定N个课程，以及它们的课程强度，

给定M个考场，以及它们的容量；

将课程分配给考场。时间复杂度的上界为O(MN )，空间复杂度的上界为O(1)。

我试图用类似于Task scheduling problem using greedy choice的方法来解决这个问题。但是基于贪心选择的任务调度问题的运行时间复杂度是n，而我喜欢用O(MN )的时间复杂度和O(1)的空间复杂度来解决这个问题。

请建议一种方法和数据结构来解决这个问题。

Answer 1

假设N>M，假设每个大厅只能分配一个班级，假设所有班级同时进行，假设您的目标是最大限度地减少空座位的数量，您可以通过识别以下属性开始：

如果" A“是具有最大尺寸的考场，而"B”是可以容纳其中的最大类，则存在一个最优解，其中B被分配给A。

为什么？假设我们有一个最优解，其中B没有被分配给A。如果B被分配到不同的教室"X"，而班级"Y“被分配到大厅" A "，那么我们可以交换班级，并且仍然有一个最优解，因为Y <= B <= X <= A。如果B没有分配到任何教室，那么我们可以将它与最大教室中的班级交换，解决方案将得到改进；因此，它从一开始就不是最优解(除非大小相等)。

现在我们知道了这一点，我们可以递归地应用它。在将尽可能大的班级放在最大的考场中之后，我们最终得到了一组新的可用班级和考场，我们可以重复这个过程。

因此，一种可能的算法如下所示：

1. 按学生人数降序排序考场: O(M
2. M)每个考场的
3. ：O(M)
   • 选择适合的最大课程:O(N)
   • 从日志中删除该课程

​

所以在这一端这是O(M log M+ NM)，这是一个比O(NM log M)更小的类。