0

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

给定 N 门课程，连同他们的课程强度，

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

将课程分配到考场。上限时间复杂度必须为 O(MN log M)，空间复杂度为 O(1)。

我尝试使用贪婪选择以类似于任务调度问题的方式解决这个问题。但是使用贪心选择的任务调度问题的运行时间复杂度为 n log n，但我喜欢使用时间复杂度 O(MN log M) 和空间复杂度 O(1) 来解决问题。

请提出解决此问题的方法和数据结构。

4

1 回答 1

2

假设 N>M，并且假设每个大厅只能分配一个班级，并且假设所有班级同时进行，并且假设您的目标是尽量减少空座位的数量，您可以从认识以下性质开始：

如果“A”是最大的考场，“B”是最大的类，则存在一个最优解，其中 B 分配给 A。

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

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

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

  1. 按学生人数降序排列考场：O(M log M)
  2. 每个考场：O(M)
    • 选择适合它的最大可能课程：O(N)
    • 从列表中删除该课程

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

于 2013-10-22T15:20:46.850 回答