Meeting Rooms II
你会得到一个会议列表，分为两个数组：第 i 个会议从 starts[i] 开始，到 ends[i] 结束。一个房间同一时间只能容纳一个会议；某个会议可以在另一个会议结束的那一刻，立即在同一房间开始。
编写一个名为 minMeetingRooms 的函数，返回容纳所有会议所需的最少房间数。
函数
- startsinteger-array
- 每场会议的开始时间
- endsinteger-array
- 每场会议的结束时间，与其开始时间的索引相同
- 返回值integer
- 能容纳所有会议的最少房间数
约束条件
1 ≤ starts.length == ends.length ≤ 50000 ≤ starts[i] < ends[i] ≤ 106- 会议没有排序。两场会议可能完全相同。
示例
- 输入
- starts = [4, 1, 7, 2]ends = [8, 5, 9, 6]
- 输出
- 3
- 解释
- 在时间 4，时间段为 1 到 5、2 到 6 和 4 到 8 的会议都在进行，因此你至少需要
3间会议室。3 间就够了：时间段为 7 到 9 的会议可以使用在时间 5 腾出的会议室。
- 输入
- starts = [12, 10, 14]ends = [14, 12, 16]
- 输出
- 1
- 解释
- 会议时间分别是 10 到 12 点、12 到 14 点和 14 到 16 点。每场会议都在上一场结束时立即开始，所以一个会议室就能容纳这三场会议。
- 输入
- starts = [0, 2, 3]ends = [10, 3, 5]
- 输出
- 2
- 解释
- 从 0 到 10 的会议全程占用一个房间。从 2 到 3 和从 3 到 5 的会议共用第二个房间，因此
2个房间就够了。
进阶
你还能指出每场会议安排在哪个房间吗？使用的房间数不要超过答案给出的数量。
提示
逐个打开提示，每个都会多透露一点。
任何时候，每场正在进行的会议都需要一个独立的会议室。一天中最繁忙的时刻能告诉你答案是什么？
按开始时间的顺序逐个处理会议。会议开始时，唯一值得检查的是最先空出来的房间。
将每个会议室的结束时间保存在最小堆中。如果最小的结束时间早于或等于下一个会议的开始时间，该会议室就空闲了：将它的结束时间替换为新会议的结束时间。否则，推入一个新的结束时间。堆的大小就是答案。
题解
你需要的会议室数量，等于同一时刻正在进行的会议数的最大值。每次会议开始时都统计正在进行的会议，耗时为 O(n²)。排序后，你可以从头到尾遍历一天，并用一个存储会议室空闲时间的最小堆，或用两个分别按开始时间和结束时间排序的列表，将耗时降至 O(n log n)。
统计每个开始时间进行中的会议数量
结果正确，但无法在最大的测试中运行完毕
思路
正在进行的会议数量只会在会议开始时增加，因此最繁忙的时刻就是某个会议的开始时间。对于每个会议 i，统计满足 starts[j] ≤ starts[i] < ends[j] 的会议 j 数量。恰好在 starts[i] 结束的会议不计入：它的会议室已经空出来了。在第一个示例中，时间 4 有 3 个正在进行的会议，时间 7 有 2 个，因此答案是 3。
n 个会议中的每一个都会扫描全部 n 个会议：当 n = 5000 时，意味着要检查 2500 万次。
算法
- 对于每场会议
i，将running设为0。 - 对于每场会议
j，当starts[j] ≤ starts[i] < ends[j]时，将running加 1。 - 保留你见过的
running最大值。 - 返回这个最大值。
def minMeetingRooms(starts, ends):
n = len(starts)
most = 0
for i in range(n):
# how many meetings are running at the moment meeting i starts
running = 0
for j in range(n):
if starts[j] <= starts[i] < ends[j]:
running += 1
most = max(most, running)
return most房间空闲时间的最小堆
思路
按开始时间依次处理会议，只看最先空出的会议室。如果会议开始时它还在使用，那么所有会议室都在使用，你就新开一间。如果它空闲，任何空闲的会议室都一样好：后续会议的开始时间都不会更早，所以现在空闲的会议室对它们来说也会一直空闲。
最小堆为每个会议室保存一个结束时间，并返回最小值。在第一个示例中，按开始时间排序后，堆会增长到 [5, 6, 8]。从 7 到 9 的会议发现 5 不晚于 7，于是将其替换，堆变为 [6, 8, 9]：需要 3 间会议室。排序需要 O(n log n)，每场会议执行一次 O(log n) 的堆操作。
算法
- 按开始时间对会议排序，并让每个开始时间与对应的结束时间保持配对。
- 对于每场会议，如果堆不为空，且其中最小的结束时间不晚于该会议的开始时间，就用该会议的结束时间替换它。
- 否则，将该会议的结束时间推入堆中：这时会新开一个会议室。
- 返回堆的大小，堆中的每个元素对应一个会议室。
import heapq
def minMeetingRooms(starts, ends):
meetings = sorted(zip(starts, ends)) # by start time
free_at = [] # a min-heap: when each room's last meeting ends
for start, end in meetings:
if free_at and free_at[0] <= start:
heapq.heapreplace(free_at, end) # the earliest free room is free now: reuse it
else:
heapq.heappush(free_at, end) # every room is busy: open a new one
return len(free_at)分别对开始时间和结束时间进行排序
思路
答案是一个计数值，因此每次有会议开始时，你只需要知道此时是否有会议已经结束，而不需要知道是哪一个会议。将开始时间和结束时间分别排序成两个列表，然后用指针 ended 遍历开始时间。会议开始时间大于或等于 endTimes[ended] 时，就使用因此空出的会议室；否则就启用一个新的会议室。
这个计数是准确的。rooms 增加时，下一个结束时间仍在未来，因此那一刻所有 rooms 个会议都在进行。只有在某个实际结束时间小于或等于当前开始时间、腾出了一间会议室时，新的会议开始才不需要启用新会议室。在第一个示例中，开始时间 1、2 和 4 都早于结束时间 5，因此 rooms 会达到 3；开始时间 7 则会重新使用在 5 时腾出的会议室。两次排序的时间复杂度为 O(n log n)，遍历的时间复杂度为 O(n)。
算法
- 分别对开始时间和结束时间的副本进行排序。
- 将
rooms和ended设为0。 - 按顺序遍历每个开始时间。如果它大于或等于
endTimes[ended]，就将ended加 1：这场会议使用一间刚空出来的房间。 - 否则，将
rooms加 1。 - 返回
rooms。
def minMeetingRooms(starts, ends):
start_times = sorted(starts)
end_times = sorted(ends)
rooms = 0
ended = 0 # how many meetings have ended, earliest end first
for start in start_times:
if start >= end_times[ended]:
ended += 1 # a meeting has ended by now: this one takes its room
else:
rooms += 1 # every room is busy: open a new one
return rooms
易错点和边界情况
- 检查
start > end，而不是start ≥ end。这样，会议结束腾出房间后，下一场会议就无法立即使用它，时间为 10 到 12、12 到 14 和 14 到 16 的会议会占用 2 个房间，而不是 1 个。 - 检查你最后打开的房间，而不是最先空出来的房间。对于时间为 1 到 3、2 到 10 和 4 到 6 的会议，虽然第一个房间从 3 点起就空出来了，你却在 4 点又开了第三个房间。
- 用与同一场会议重叠的会议数加 1 作为答案。时间为 0 到 10 的会议与时间为 2 到 3 和 3 到 5 的会议重叠，但后两场会议从不重叠，所以 2 个房间就够了。
常见问题3
会议室 II 的时间复杂度是多少？
堆和双列表解法的运行时间都是 O(n log n)，额外空间都是 O(n)。主要耗时在排序上；排序后的遍历使用堆时需要 O(n log n) 时间，使用两个列表时需要 O(n) 时间。
“Meeting Rooms II” 可以用扫描线算法解决吗？
是的。将每场会议在开始时转换为 +1 事件，在结束时转换为 -1 事件，然后对这些事件排序，并跟踪运行总数的最大值。时间相同时，先处理结束事件，再处理开始事件，这样时间相接的会议就能共用一个会议室。
这个答案是否等于同一时间重叠的会议最多数量？
是的。同时进行的会议需要不同的会议室，所以至少需要这么多间。按开始时间的顺序，为每场会议分配任意一间空闲会议室，不会需要更多会议室，因此重叠会议的峰值数量正好就是答案。
def minMeetingRooms(starts, ends):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
starts = [4, 1, 7, 2] ends = [8, 5, 9, 6]
预期输出
3