題目出處
難度
medium
個人範例程式碼
from typing import (
List,
)
from lintcode import (
Interval,
)
"""
Definition of Interval:
class Interval(object):
def __init__(self, start, end):
self.start = start
self.end = end
"""
class Solution:
"""
@param intervals: an array of meeting time intervals
@return: the minimum number of conference rooms required
"""
def min_meeting_rooms(self, intervals: List[Interval]) -> int:
# Write your code here
if not intervals:
return 0
time_table = []
for interval in intervals:
time_table.append((interval.start, +1))
time_table.append((interval.end, -1))
time_table.sort(key=lambda x: x[0])
ans = 0
booked_room = 0
for time, room_used in time_table:
booked_room += room_used
ans = max(ans, booked_room)
return ans
或者,我們也可以用 hashtable 來記錄 (概念相同)
from typing import (
List,
)
from lintcode import (
Interval,
)
"""
Definition of Interval:
class Interval(object):
def __init__(self, start, end):
self.start = start
self.end = end
"""
class Solution:
"""
@param intervals: an array of meeting time intervals
@return: the minimum number of conference rooms required
"""
def min_meeting_rooms(self, intervals: List[Interval]) -> int:
# Write your code here
if not intervals:
return 0
time_table = collections.defaultdict(int)
for interval in intervals:
time_table[interval.start] += 1
time_table[interval.end] -= 1
# print(time_table)
ans = 0
used_room = 0
for time in sorted(time_table.keys()):
used_room += time_table[time]
ans = max(ans, used_room)
return ans
算法說明
- 這題目有前一題單純只判斷有沒有重複會議室,而這題是要直接計算所需要的會議室數量,上一題可參考:
現在要安排需要的會議室數量,
我們可以直接把所有的時間點 (start, end) 都存入一個 table 裡面,排序後就可以得到我們要的答案。
儲存的方式為 (start_time, +1), (end_time, +1),
最後我們只要將第一個欄位的 time 排序即可。
之後我們可以再使用 +1, -1 去判斷個時段的會議室增減。
input handling
如果沒有 intervals, 回傳 0 (題目沒特別要求)
Boundary conditions
用 for 迴圈控制範圍
Reference
⭐ Leetcode 解題紀錄 ⭐ | 題型 | 資料結構 | Python Solution | C++ Solution | Note | |
---|---|---|---|---|---|---|
⭐BFS 相關題型 ⭐ | ||||||
104 | Maximum Depth of Binary Tree | BFS (分層) | Python | |||
94 | Binary Tree Inorder Traversal | BFS (分層) | Tree | Python | 內含 處理 Tree 樹問題的重點 | |
102 | Binary Tree Level Order Traversal | BFS (分層) | Tree | Python | ||
103 | Binary Tree Zigzag Level Order Traversal | BFS (分層) | Tree | Python | ||
107 | Binary Tree Level Order Traversal II | BFS (分層) | Tree | Python | ||
133 | Clone Graph | BFS (分層) | Graph | Python | Graph 的基本操作 #重要題型 | |
127 | Word Ladder |