Joh*_*nce 2 algorithm greedy time-complexity
所以问题是这样的：
我们有 n 个班级（n 个间隔），开始时间和结束时间为 [si , fi]，我们希望找到能够满足所有班级（间隔）且没有任何串通的教室的最小数量
我正在读的书说我们可以在 O(nlogn) 中解决这个问题，但我找不到比 O(n^2) 更好的算法
它说我们应该按开始时间对它们进行排序，但没有说解决方案的其余部分，但这没有任何意义，因为在给每个班级一个房间之前，我们不应该检查所有其他时间间隔，看看是否我们有没有串通？这使得它的复杂度为 O(n^2) 因为对于每个间隔我们需要检查所有其他间隔
我错过了什么吗？
您可以按时间对事件进行排序（事件可以是课程的开始或课程的结束）。这将花费 O(n log n)。
现在，保留一堆空房间并按顺序经历事件：
第二阶段可以在 O(n) 内完成。
通过跟踪已完成的分配和取消分配，您可以轻松找到所需房间的数量和时间表。
如果您只需要所需房间的数量，则可以简化为仅使用计数器而不是房间列表。每个开始事件加1，每个结束事件减1；跟踪最大值。