如何用O(nlogn)复杂度求解n个课程区间调度的最小教室数？

我来给你详细拆解这个问题的高效解法，核心是**贪心策略+最小堆（优先队列）**的组合，比你之前的O(n²)方法高效很多。

核心思路 #

我们的目标是尽可能复用已有的教室，而非每次都新增。通过跟踪每个教室的最晚结束时间，就能快速判断是否有教室能承接当前课程。

具体步骤 #

1. 排序课程
   把所有课程按照开始时间从小到大排序；如果两个课程开始时间相同，按结束时间从小到大排序。这一步的时间复杂度是O(nlogn)，是整个算法的基础。

2. 用最小堆跟踪教室结束时间
   最小堆的特性是堆顶元素始终是当前所有教室中结束最早的时间，这样我们能最快判断是否有教室可以复用。

3. 遍历处理每个课程
   对每个排序后的课程，做以下判断：

   • 如果当前课程的开始时间 ≥ 堆顶的结束时间：说明这个最早空闲的教室可以用来上当前课程，把堆顶的结束时间弹出，再把当前课程的结束时间加入堆（更新这个教室的结束时间）。
   • 如果当前课程的开始时间 < 堆顶的结束时间：说明所有教室都还在占用，必须新增一个教室，直接把当前课程的结束时间加入堆。

4. 最终结果
   遍历完成后，堆的大小就是我们需要的最小教室数量。

复杂度分析 #

• 排序阶段：O(nlogn)
• 堆操作阶段：每个课程最多入堆和出堆各一次，每次堆操作的时间是O(logk)（k是当前堆的大小，最大为n），这部分总时间是O(nlogn)
• 整体复杂度：O(nlogn)，完全符合你要的高效要求。

举个例子理解 #

假设我们有4个课程：

• 课程A: [9, 10]
• 课程B: [9, 12]
• 课程C: [10, 11]
• 课程D: [11, 13]

1. 排序后顺序是A、B、C、D
2. 处理A：堆为空，加入10，堆大小=1
3. 处理B：开始时间9 < 10，新增教室，加入12，堆大小=2
4. 处理C：开始时间10 ≥10，弹出10，加入11，堆大小=2
5. 处理D：开始时间11 ≥11，弹出11，加入13，堆大小=2

最终堆大小是2，也就是只需要2个教室，完全正确。

对比O(n²)方法 #

你之前的O(n²)方法应该是对每个课程，遍历所有已分配的教室看是否有空，这种方法在课程数量多的时候效率很低。而用最小堆的话，每次判断只需要看堆顶，堆操作的效率远高于线性遍历。

内容的提问来源于stack exchange，提问作者John Pence