題目出處
難度
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
算法說明
- 這題目有前一題單純只判斷有沒有重複會議室，而這題是要直接計算所需要的會議室數量，上一題可參考：
https://wongwongnotes-github-io.pages.dev/python/python_leetcode/lintcode-python-920/
現在要安排需要的會議室數量，
我們可以直接把所有的時間點 (start, end) 都存入一個 table 裡面，排序後就可以得到我們要的答案。
儲存的方式為 (start_time, +1), (end_time, +1)，
最後我們只要將第一個欄位的 time 排序即可。
之後我們可以再使用 +1, -1 去判斷個時段的會議室增減。
input handling
如果沒有 intervals, 回傳 0 (題目沒特別要求)
Boundary conditions
用 for 迴圈控制範圍