是否有一种算法可以在 O(nlogn) 中找到调度 n 类 的最少教室数？
Is there an Algorithm for finding the minimum number of classrooms for scheduling n classes in O(nlogn)?
所以问题是这样的：
我们有 n classes（n 个间隔）开始时间和结束时间 [si , fi] 并且我们想要找到满足所有条件的最小 class 房间数classes(intervals) 没有任何勾结
我正在阅读的书说我们可以在 O(nlogn) 中解决这个问题，但我找不到比 O(n^2) 更好的算法
它说我们应该按开始时间对它们进行排序，但没有说解决方案的其余部分，但这没有任何意义，因为在给每个 class 一个房间之前，我们不应该检查所有其他间隔，看看我们是否有勾结？这使得它成为 O(n^2) 因为对于每个间隔我们需要检查所有其他间隔
我是不是漏了什么？
您可以按时间对事件进行排序（一个事件可以是 class 的开始，也可以是 class 的结束）。这将花费 O(n log n).
现在，保留一堆空房间并按顺序完成事件：
- 对于每个开始事件，从空堆栈中取出一个房间并将 class 分配给它。
- 对于每个结束事件，将相应的房间放回空堆栈。
第二阶段可以在 O(n) 内完成。
通过跟踪已完成的分配和解除分配，您可以轻松找到所需房间的数量和时间表。
如果您只需要所需房间的数量，这可以简化为只使用计数器而不是房间列表。每个开始事件加一，每个结束事件减一；跟踪最大值。
第一步：将classes的起点和终点分别存储在actions数组中。如果该点是起点，则 action 的 type 是 +1，否则，如果它是 class 的终点，则其 type 是 -1。
第二步：将actions数组按时间升序排序。如果时间相等，则按 type 升序排序。
第三步：将counter置0，遍历actions数组，如果是起始类型counter加1，如果是finishing类型从中减1柜台。同样，如果时间相等，首先执行整理类型。因为您可以在那个房间的 class 结束后立即使用同一个 class 房间。
计数器达到的最大值就是你的答案。
这里是python算法的实现：
classess = [ [13, 15], [11, 13], [4, 7], [2, 4], [3, 6] ]
# construct a action list:
# action[0] -> time of action
# action[1] -> type of action (-1 for finish type, 1 for start type)
actions = []
for cla55 in classess:
actions.append([cla55[0], 1])
actions.append([cla55[1], -1])
actions.sort()
# [[2, 1], [3, 1], [4, -1], [4, 1], [6, -1], [7, -1], [11, 1], [13, -1], [13, 1], [15, -1]]
min_classrooms = 0
curr_classrooms = 0
for action in actions:
curr_classrooms += action[1]
if curr_classrooms > min_classrooms:
min_classrooms = curr_classrooms
print(min_classrooms)
所以问题是这样的：
我们有 n classes（n 个间隔）开始时间和结束时间 [si , fi] 并且我们想要找到满足所有条件的最小 class 房间数classes(intervals) 没有任何勾结
我正在阅读的书说我们可以在 O(nlogn) 中解决这个问题，但我找不到比 O(n^2) 更好的算法
它说我们应该按开始时间对它们进行排序，但没有说解决方案的其余部分，但这没有任何意义，因为在给每个 class 一个房间之前，我们不应该检查所有其他间隔，看看我们是否有勾结？这使得它成为 O(n^2) 因为对于每个间隔我们需要检查所有其他间隔
我是不是漏了什么？
您可以按时间对事件进行排序（一个事件可以是 class 的开始，也可以是 class 的结束）。这将花费 O(n log n).
现在，保留一堆空房间并按顺序完成事件：
- 对于每个开始事件，从空堆栈中取出一个房间并将 class 分配给它。
- 对于每个结束事件，将相应的房间放回空堆栈。
第二阶段可以在 O(n) 内完成。
通过跟踪已完成的分配和解除分配，您可以轻松找到所需房间的数量和时间表。
如果您只需要所需房间的数量，这可以简化为只使用计数器而不是房间列表。每个开始事件加一，每个结束事件减一；跟踪最大值。
第一步：将classes的起点和终点分别存储在actions数组中。如果该点是起点，则 action 的 type 是 +1，否则，如果它是 class 的终点，则其 type 是 -1。
第二步：将actions数组按时间升序排序。如果时间相等，则按 type 升序排序。
第三步：将counter置0，遍历actions数组，如果是起始类型counter加1，如果是finishing类型从中减1柜台。同样，如果时间相等，首先执行整理类型。因为您可以在那个房间的 class 结束后立即使用同一个 class 房间。
计数器达到的最大值就是你的答案。
这里是python算法的实现：
classess = [ [13, 15], [11, 13], [4, 7], [2, 4], [3, 6] ]
# construct a action list:
# action[0] -> time of action
# action[1] -> type of action (-1 for finish type, 1 for start type)
actions = []
for cla55 in classess:
actions.append([cla55[0], 1])
actions.append([cla55[1], -1])
actions.sort()
# [[2, 1], [3, 1], [4, -1], [4, 1], [6, -1], [7, -1], [11, 1], [13, -1], [13, 1], [15, -1]]
min_classrooms = 0
curr_classrooms = 0
for action in actions:
curr_classrooms += action[1]
if curr_classrooms > min_classrooms:
min_classrooms = curr_classrooms
print(min_classrooms)