algorithm - 是否有一种算法可以在 O(nlogn) 中找到安排 n 个类(class)的最少教室数？

Question

所以问题是:

我们有 n 个类(class)(n 个间隔)，开始时间和结束时间为 [si , fi]，我们想找到最少的教室数量，我们可以在没有任何串通的情况下满足所有类(class)(间隔)

我正在阅读的书说我们可以在 O(nlogn) 中解决这个问题，但我找不到比 O(n^2) 更好的算法

它说我们应该按开始时间对它们进行排序，但没有说解决方案的其余部分，但这没有任何意义，因为在给每个类(class)一个房间之前，我们不应该检查所有其他间隔以看看我们有没有勾结？这使得它成为 O(n^2) 因为对于每个间隔我们需要检查所有其他间隔

我错过了什么吗？

Answer 1

您可以按时间对事件进行排序(一个事件可以是一节课的开始，也可以是一节课的结束)。这将花费 O(n log n)。

现在，保留一堆空房间并按顺序处理事件:

• 对于每个开始事件，从空堆栈中取出一个房间并将类分配给它。
• 对于每个结束事件，将相应的房间放回空堆栈。

第二阶段可以在 O(n) 内完成。

通过跟踪已完成的分配和解除分配，您可以轻松找到所需房间的数量和时间表。

如果您只需要所需房间的数量，这可以简化为只使用计数器而不是房间列表。每个开始事件加一，每个结束事件减一；跟踪最大值。