所以问题是:
我们有 n 个类(class)(n 个间隔),开始时间和结束时间为 [si , fi],我们想找到最少的教室数量,我们可以在没有任何串通的情况下满足所有类(class)(间隔)
我正在阅读的书说我们可以在 O(nlogn) 中解决这个问题,但我找不到比 O(n^2) 更好的算法
它说我们应该按开始时间对它们进行排序,但没有说解决方案的其余部分,但这没有任何意义,因为在给每个类(class)一个房间之前,我们不应该检查所有其他间隔以看看我们有没有勾结?这使得它成为 O(n^2) 因为对于每个间隔我们需要检查所有其他间隔
我错过了什么吗?
最佳答案
您可以按时间对事件进行排序(一个事件可以是一节课的开始,也可以是一节课的结束)。这将花费 O(n log n)。
现在,保留一堆空房间并按顺序处理事件:
- 对于每个开始事件,从空堆栈中取出一个房间并将类分配给它。
- 对于每个结束事件,将相应的房间放回空堆栈。
第二阶段可以在 O(n) 内完成。
通过跟踪已完成的分配和解除分配,您可以轻松找到所需房间的数量和时间表。
如果您只需要所需房间的数量,这可以简化为只使用计数器而不是房间列表。每个开始事件加一,每个结束事件减一;跟踪最大值。
关于algorithm - 是否有一种算法可以在 O(nlogn) 中找到安排 n 个类(class)的最少教室数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49379783/