2402. 会议室 III #

链接 #

2402. 会议室 III

题目 #

给你一个整数 n ，共有编号从 0 到 n - 1 的 n 个会议室。

给你一个二维整数数组 meetings ，其中 meetings[i] = [starti, endi] 表示一场会议将会在半闭时间区间 [starti, endi) 举办。所有 starti 的值 互不相同 。

会议将会按以下方式分配给会议室：

每场会议都会在未占用且编号最小的会议室举办。
如果没有可用的会议室，会议将会延期，直到存在空闲的会议室。延期会议的持续时间和原会议持续时间相同。
当会议室处于未占用状态时，将会优先提供给原开始时间更早的会议。

返回举办最多次会议的房间编号。如果存在多个房间满足此条件，则返回编号最小的房间。

半闭区间 [a, b) 是 a 和 b 之间的区间，包括 a 但 不包括 b 。

示例 1：

输入：n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
输出：0
解释：
- 在时间 0 ，两个会议室都未占用，第一场会议在会议室 0 举办。
- 在时间 1 ，只有会议室 1 未占用，第二场会议在会议室 1 举办。
- 在时间 2 ，两个会议室都被占用，第三场会议延期举办。
- 在时间 3 ，两个会议室都被占用，第四场会议延期举办。
- 在时间 5 ，会议室 1 的会议结束。第三场会议在会议室 1 举办，时间周期为 [5,10) 。
- 在时间 10 ，两个会议室的会议都结束。第四场会议在会议室 0 举办，时间周期为 [10,11) 。
会议室 0 和会议室 1 都举办了 2 场会议，所以返回 0 。

示例 2：

输入：n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
输出：1
解释：
- 在时间 1 ，所有三个会议室都未占用，第一场会议在会议室 0 举办。
- 在时间 2 ，会议室 1 和 2 未占用，第二场会议在会议室 1 举办。
- 在时间 3 ，只有会议室 2 未占用，第三场会议在会议室 2 举办。
- 在时间 4 ，所有三个会议室都被占用，第四场会议延期举办。
- 在时间 5 ，会议室 2 的会议结束。第四场会议在会议室 2 举办，时间周期为 [5,10) 。
- 在时间 6 ，所有三个会议室都被占用，第五场会议延期举办。
- 在时间 10 ，会议室 1 和 2 的会议结束。第五场会议在会议室 1 举办，时间周期为 [10,12) 。
会议室 1 和会议室 2 都举办了 2 场会议，所以返回 1 。

提示：

1 <= n <= 100
1 <= meetings.length <= 105
meetings[i].length == 2
0 <= starti < endi <= 5 * 105
starti 的所有值 互不相同

用效率最优且代码最简洁的方式实现，并详细介绍你的思路，代码注释

解答 #

可以使用优先队列（最小堆）来存储每个会议室的结束时间。我们首先按照开始时间对会议进行排序，然后遍历所有会议，对于每个会议，我们检查当前可用的最早结束时间的会议室是否可用。如果可用，我们更新该会议室的结束时间；如果不可用，我们为这个会议安排一个新的会议室，并将其结束时间加入优先队列。最后，我们返回举办最多次会议的房间编号。

from heapq import heappush, heappop
from typing import List

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        # 初始化会议室计数器和空闲、使用中的会议室列表
        room_counts = [0] * n
        idle_rooms = list(range(n)) # 空闲会议室的编号，也是最小堆，这样弹出时得到的是最小编号
        active_rooms = [] # 会议室的结束时间和编号的最小堆，弹出得到的是最早结束的会议室

        # 按照开始时间对会议进行排序
        meetings.sort(key=lambda m: m[0])
        
        for start, end in meetings:
            # 每到一个时间点，我们就计算一下当前空闲的会议室是否有一个或多个会议结束
            while active_rooms and active_rooms[0][0] <= start:
                room = heappop(active_rooms)[1]
                heappush(idle_rooms, room)

            # 尝试获取一个空闲的会议室
            room_idx = heappop(idle_rooms) if idle_rooms else None
            if room_idx is None:
                earliest_end, room_idx = heappop(active_rooms)
                end = end - start + earliest_end

            # 更新统计值和占用的会议室结束时间
            room_counts[room_idx] += 1
            heappush(active_rooms, (end, room_idx))

        return room_counts.index(max(room_counts))

时间复杂度：O(n+m(log⁡n+log⁡m))，其中 m 为 meetings 的长度。注意每个会议至多入堆出堆各一次。空间复杂度：O(n)O(n)O(n)。

本题题解原作者：https://leetcode.cn/problems/meeting-rooms-iii/solutions/1799420/shuang-dui-mo-ni-pythonjavacgo-by-endles-ctwc/

代码编写过程拆解 #

首先我们会想到，为了得到最终结果，需要一个 room_count 变量来记录每个会议室的使用次数。我们可以使用一个长度为 n 的数组来记录每个会议室的使用次数，初始化为 0。
同时排序也安排上，方便对会议进行时间顺序的遍历。

from typing import List

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        room_counts = [0] * n
        meetings.sort(key=lambda m: m[0])

        for start, end in meetings:
            ...

        return room_counts.index(max(room_counts))

接下来我们想的是怎么安排每一个会议。那就分成两个情况，有空闲和无空闲：

from heapq import heappush, heappop
from typing import List

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        room_counts = [0] * n
        meetings.sort(key=lambda m: m[0])

        for start, end in meetings:
            if not is_free(start):
                rearrange((new_start, new_end))
            else:
                room = get_room()
                occupy(room)

        return room_counts.index(max(room_counts))

为了获取一个空闲的 room，我们自然想到使用一个最小堆来存储空闲的会议室编号。
同时，我们还需要一个最小堆来存储使用中的会议室的结束时间和编号。这样我们就可以在 O(1) 的时间内获取最早结束的会议室。
自然的，is_free(room) 的判断标准就是当前时间是否小于最早结束的会议室的结束时间。考虑到可能有多个会议室同时结束，我们需要使用一个 while 循环来处理。

from heapq import heappush, heappop
from typing import List

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        room_counts = [0] * n
        meetings.sort(key=lambda m: m[0])

        for start, end in meetings:

            if not room_idx:
                rearrange((new_start, new_end))
            else:
                occupy(room_idx)

        return room_counts.index(max(room_counts))

from heapq import heappush, heappop
from typing import List

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        room_counts = [0] * n
        meetings.sort(key=lambda m: m[0])

        for start, end in meetings:
            
            if not room_idx:
                rearrange((new_start, new_end))
            else:
                occupy(room_idx)

        return room_counts.index(max(room_counts))


from heapq import heappush, heappop
from typing import List

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        room_counts = [0] * n
        meetings.sort(key=lambda m: m[0])
        idle_rooms = range(n)
        active_rooms = []
        I_END_TIME = 0
        I_ROOM_IDX

        for start, end in meetings:
            while active_rooms and active_rooms[0][I_END_TIME] < start:
                heappush(idle_rooms, heappop(active_rooms)[I_ROOM_IDX])
                
            if not room_idx:
                rearrange((new_start, new_end))
            else:
                occupy(room_idx)

        return room_counts.index(max(room_counts))


from heapq import heappush, heappop
from typing import List

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        room_counts = [0] * n
        meetings.sort(key=lambda m: m[0])
        idle_rooms = list(range(n))
        active_rooms = []
        I_END_TIME = 0
        I_ROOM_IDX = 1

        for start, end in meetings:
            while active_rooms and active_rooms[0][I_END_TIME] <= start:
                heappush(idle_rooms, heappop(active_rooms)[I_ROOM_IDX])
            room_idx = heappop(idle_rooms) if idle_rooms else None

            if room_idx is None:
                earliest_end, room_idx = heappop(active_rooms)
                end = end - start + earliest_end

            room_counts[room_idx] += 1
            heappush(active_rooms, (end, room_idx))

        return room_counts.index(max(room_counts))

于是得到了最终代码。按照编写思路得到的最终代码可能每次都略有不同，但是思路是一样的，也都能得到正确的结果。