項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 widget-area-1 尚未註冊或是沒有一個 view.php 檔案.
項目 search-input 尚未註冊或是沒有一個 view.php 檔案.

【Lintcode】python – [919] Meeting Rooms II 個人解法筆記

題目出處

919 · Meeting Rooms II

難度

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

算法說明

  • 這題目有前一題單純只判斷有沒有重複會議室,而這題是要直接計算所需要的會議室數量,上一題可參考:

【Lintcode】python – [920] Meeting Rooms 個人解法筆記

現在要安排需要的會議室數量,
我們可以直接把所有的時間點 (start, end) 都存入一個 table 裡面,排序後就可以得到我們要的答案。

儲存的方式為 (start_time, +1), (end_time, +1),
最後我們只要將第一個欄位的 time 排序即可。

之後我們可以再使用 +1, -1 去判斷個時段的會議室增減。

input handling

如果沒有 intervals, 回傳 0 (題目沒特別要求)

Boundary conditions

用 for 迴圈控制範圍

Reference

⭐ Leetcode 解題紀錄 ⭐題型資料結構Python SolutionC++ SolutionNote
⭐BFS 相關題型 ⭐
104Maximum Depth of Binary TreeBFS (分層)Python
94Binary Tree Inorder TraversalBFS (分層)TreePython 內含 處理 Tree 樹問題的重點
102Binary Tree Level Order TraversalBFS (分層)TreePython
103Binary Tree Zigzag Level Order TraversalBFS (分層)TreePython
107Binary Tree Level Order Traversal IIBFS (分層)TreePython
133Clone GraphBFS (分層)GraphPython Graph 的基本操作 #重要題型
127Word Ladder