歡迎關(guān)注 leetcode 專欄
題目
給定一個(gè)會(huì)議時(shí)間安排的數(shù)組爬舰，每個(gè)會(huì)議時(shí)間都會(huì)包括開始和結(jié)束的時(shí)間 [[s1,e1],[s2,e2],...] (si < ei)，為避免會(huì)議沖突，同時(shí)要考慮充分利用會(huì)議室資源，請(qǐng)你計(jì)算至少需要多少間會(huì)議室，才能滿足這些會(huì)議安排。
示例 1:
輸入: [[0, 30],[5, 10],[15, 20]]
輸出: 2
示例 2:
輸入: [[7,10],[2,4]]
輸出: 1
鏈接：https://leetcode-cn.com/problems/meeting-rooms-ii
解法
常規(guī)解法
思路就是：
- 對(duì)所有會(huì)議，按照開始時(shí)間排升序俏站；
- 用貪心算法，每來(lái)一個(gè)新的會(huì)議痊土，遍歷所有會(huì)議室肄扎，如果有空的會(huì)議室（該會(huì)議室的結(jié)束時(shí)間早于等于當(dāng)前會(huì)議的開始時(shí)間），則作為當(dāng)前最優(yōu)的選擇施戴，更新該會(huì)議室的結(jié)束時(shí)間反浓，并停止循環(huán)
- 如果一個(gè)可用的會(huì)議室都沒有，則新增會(huì)議室赞哗，并更新該會(huì)議室的結(jié)束時(shí)間雷则。
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
rooms = [] # 記錄各會(huì)議室的結(jié)束時(shí)間
meetings = sorted(intervals, key=lambda x: x[0]) # 按開始時(shí)間升序
for meeting in meetings:
find = False
for index, end_time in enumerate(rooms):
# 找到滿足結(jié)束時(shí)間早于當(dāng)前會(huì)議開始時(shí)間的會(huì)議室，并更新會(huì)議室的時(shí)間表
if end_time <= meeting[0]:
rooms[index] = meeting[1]
find = True
break
# 如果沒找到肪笋，則新增會(huì)議室
if not find:
rooms.append(meeting[1])
return len(rooms)
時(shí)間復(fù)雜度為 O(N^2)月劈，分為兩個(gè)部分：
- 對(duì)長(zhǎng)度為 N 的會(huì)議進(jìn)行排序度迂，復(fù)雜度為 O(N*logN)
1， 對(duì) N 個(gè)會(huì)議分別執(zhí)行查找和插入操作猜揪，最差情況下任意兩兩會(huì)議的時(shí)間都是沖突的惭墓，那么對(duì)第 i 個(gè)會(huì)議的查找次數(shù)為 i 次，1+2+...+n=n(n+1)/2而姐，全程共插入 n(n+1)/2 次嵌灰，插入 N 次喂窟，最差復(fù)雜度為 O(N^2) 箱熬。
空間復(fù)雜度O(n)春畔，就看 rooms 的長(zhǎng)度，最好的情況下 O(1)政鼠，最差的情況下 O(n)风瘦。
最小堆解法
import heapq
class Solution:
def minMeetingRooms(self, intervals: list) -> int:
rooms = [] # 記錄各會(huì)議室的最早結(jié)束時(shí)間
meetings = sorted(intervals, key=lambda x: x[0]) # 按開始時(shí)間升序
for meeting in meetings:
# 如果最早結(jié)束的會(huì)議室的結(jié)束時(shí)間比會(huì)議室時(shí)間要早，則先關(guān)閉該會(huì)議室
if rooms and rooms[0] <= meeting[0]:
heapq.heappop(rooms)
# 插入新的會(huì)議室到最小堆
heapq.heappush(rooms, meeting[1])
return len(rooms)
時(shí)間復(fù)雜度為O(N*logN)公般，分為兩個(gè)部分：
- 對(duì)長(zhǎng)度為 N 的會(huì)議進(jìn)行排序万搔，復(fù)雜度為 O(N*logN)
- 對(duì) N 個(gè)會(huì)議分別執(zhí)行彈出和插入操作，最差情況下任意兩兩會(huì)議的時(shí)間都是沖突的官帘，每次彈出的復(fù)雜度為 1瞬雹，每次插入的復(fù)雜度為 O(logN)，N 個(gè)會(huì)議室的總復(fù)雜度為 O(N*logN)
空間復(fù)雜度O(n)刽虹，就看 rooms 的長(zhǎng)度挖炬，最好的情況下 O(1)，最差的情況下 O(n)状婶。
優(yōu)先隊(duì)列解法
from queue import PriorityQueue
class Solution:
def minMeetingRooms(self, intervals: list) -> int:
rooms = PriorityQueue()
meetings = sorted(intervals, key=lambda x: x[0]) # 按開始時(shí)間升序
for meeting in meetings:
# 如果最早結(jié)束的會(huì)議室的結(jié)束時(shí)間比會(huì)議室時(shí)間要早，則先關(guān)閉該會(huì)議室
if rooms.qsize() and rooms.queue[0] <= meeting[0]:
rooms.get()
# 插入新的會(huì)議室到優(yōu)先隊(duì)列
rooms.put(meeting[1])
return rooms.qsize()
雖然用優(yōu)先隊(duì)列來(lái)實(shí)現(xiàn)馅巷，復(fù)雜度跟最小堆是一樣的膛虫，但是算法實(shí)際執(zhí)行的時(shí)候，耗時(shí)比較長(zhǎng)钓猬，不知道是否是內(nèi)部實(shí)現(xiàn)的時(shí)候有其他額外邏輯
更多刷題稍刀，盡在 leetcode 專欄
