leetcode 253. 会议室 II

发表于 分类于 阅读次数：

解题思路

1、将会议时间数组排序：
按start从小到大排序，当start相同时，按end从小到大排序
2、根据会议时间顺序依次安排房间：
记录每个房间释放的时间，若即将安排的会议start早于最小的释放时间，则需要新房间，否则更新房间的释放时间

贪心关键点：将 “即将安排的会议start” 与 “最小的释放时间” 做比较，尽可能避免冲突

关于贪心，可参考：https://www.jianshu.com/p/ab89df9759c8

时间复杂度

O(N*logN) N：会议时间数组长度

详细分析：
1、python sorted时间复杂度：O(N*logN)

关于sorted时间复杂度，可参考：https://www.cnblogs.com/clement-jiao/p/9243066.html

2、最坏情况下N个会议均冲突，此时heappop[0]时间复杂度：O(1)，heappush时间复杂度：O(logN)，故总的时间复杂度为O(N*logN)

关于heapq操作的时间复杂度，可参考：https://www.coder.work/article/97172

空间复杂度

O(N) N：会议时间数组长度

详细分析
1、最坏情况下N个会议均冲突，heap_queue需要存储N个数据

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        heap_queue = []

        for start, end in sorted(intervals, key=lambda item: (item[0], item[1])):
            if not heap_queue:
                heapq.heappush(heap_queue, end)
                continue
            if start >= heap_queue[0]:
                heapq.heappop(heap_queue)
            heapq.heappush(heap_queue, end)
            
        return len(heap_queue)