欢迎关注 leetcode 专栏
题目
给定一个会议时间安排的数组,每个会议时间都会包括开始和结束的时间 [[s1,e1],[s2,e2],...] (si < ei),为避免会议冲突,同时要考虑充分利用会议室资源,请你计算至少需要多少间会议室,才能满足这些会议安排。
示例 1:
输入: [[0, 30],[5, 10],[15, 20]]
输出: 2
示例 2:
输入: [[7,10],[2,4]]
输出: 1
链接:https://leetcode-cn.com/problems/meeting-rooms-ii
解法
常规解法
思路就是:
- 对所有会议,按照开始时间排升序;
- 用贪心算法,每来一个新的会议,遍历所有会议室,如果有空的会议室(该会议室的结束时间早于等于当前会议的开始时间),则作为当前最优的选择,更新该会议室的结束时间,并停止循环
- 如果一个可用的会议室都没有,则新增会议室,并更新该会议室的结束时间。
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
rooms = [] # 记录各会议室的结束时间
meetings = sorted(intervals, key=lambda x: x[0]) # 按开始时间升序
for meeting in meetings:
find = False
for index, end_time in enumerate(rooms):
# 找到满足结束时间早于当前会议开始时间的会议室,并更新会议室的时间表
if end_time <= meeting[0]:
rooms[index] = meeting[1]
find = True
break
# 如果没找到,则新增会议室
if not find:
rooms.append(meeting[1])
return len(rooms)
时间复杂度为 O(N^2),分为两个部分:
- 对长度为 N 的会议进行排序,复杂度为 O(N*logN)
1, 对 N 个会议分别执行查找和插入操作,最差情况下任意两两会议的时间都是冲突的,那么对第 i 个会议的查找次数为 i 次,1+2+...+n=n(n+1)/2,全程共插入 n(n+1)/2 次,插入 N 次,最差复杂度为 O(N^2) 。
空间复杂度O(n),就看 rooms 的长度,最好的情况下 O(1),最差的情况下 O(n)。
最小堆解法
import heapq
class Solution:
def minMeetingRooms(self, intervals: list) -> int:
rooms = [] # 记录各会议室的最早结束时间
meetings = sorted(intervals, key=lambda x: x[0]) # 按开始时间升序
for meeting in meetings:
# 如果最早结束的会议室的结束时间比会议室时间要早,则先关闭该会议室
if rooms and rooms[0] <= meeting[0]:
heapq.heappop(rooms)
# 插入新的会议室到最小堆
heapq.heappush(rooms, meeting[1])
return len(rooms)
时间复杂度为O(N*logN),分为两个部分:
- 对长度为 N 的会议进行排序,复杂度为 O(N*logN)
- 对 N 个会议分别执行弹出和插入操作,最差情况下任意两两会议的时间都是冲突的,每次弹出的复杂度为 1,每次插入的复杂度为 O(logN),N 个会议室的总复杂度为 O(N*logN)
空间复杂度O(n),就看 rooms 的长度,最好的情况下 O(1),最差的情况下 O(n)。
优先队列解法
from queue import PriorityQueue
class Solution:
def minMeetingRooms(self, intervals: list) -> int:
rooms = PriorityQueue()
meetings = sorted(intervals, key=lambda x: x[0]) # 按开始时间升序
for meeting in meetings:
# 如果最早结束的会议室的结束时间比会议室时间要早,则先关闭该会议室
if rooms.qsize() and rooms.queue[0] <= meeting[0]:
rooms.get()
# 插入新的会议室到优先队列
rooms.put(meeting[1])
return rooms.qsize()
虽然用优先队列来实现,复杂度跟最小堆是一样的,但是算法实际执行的时候,耗时比较长,不知道是否是内部实现的时候有其他额外逻辑
更多刷题,尽在 leetcode 专栏
网友评论