📆行程安排 我的行事曆II_My Calendar II_Leetcode #731

Towfiqu barbhuiya on Unsplash

題目敘述 My Calendar II

給定一個行事曆的class定義和行程安排的介面interface。

請完成下列function

1.建構子MyCalendarTwo() 初始化MyCalendarTwo物件

2.boolean book(int start, int end)

在行事曆加入一項新行程，起始時間為start, 結束時間為end。

該行程占用的時間是[start, end) 包含起點start, 不包含終點end。

如果新行程不會和舊行程重疊 或者 新行程只和舊行程重疊一次，
把新行程加入行事曆，並且回傳true。

如果新行程會和已知的兩個舊行程有重疊，則拒絕新行程，並且回傳false。

也就是說，每個時間點最多允許預約booking兩個行程，拒絕第三個行程。

測試範例

Example 1:

Input
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]

Explanation
MyCalendarTwo myCalendarTwo = new MyCalendarTwo();
myCalendarTwo.book(10, 20); // 可以，沒有和任何行程重疊。
myCalendarTwo.book(50, 60); // 可以，沒有和任何行程重疊。
myCalendarTwo.book(10, 40); // 可以，從這次排程之後，[10, 20) 被預定兩個行程。
myCalendarTwo.book(5, 15);  // 拒絕，因為[10, 15) 已經有兩個行程了。
myCalendarTwo.book(5, 10); // 可以，沒有和任何行程重疊。
myCalendarTwo.book(25, 55); // 可以，從這次排程之後，[25, 40) 和 [50,55) 被預定兩個行程。
																				

範例輔助說明

示意圖 重複的檢測

演算法 每個時間點最多允許兩個行程，拒絕第三個行程。

每個行程進來先檢查是否已經有兩個行程double_bookings和當下的行程有重疊?
如果有，直接拒絕第三個行程，返回False。

接著，檢查和已知行程single_bookings是否有重疊?

如果有，就把重疊兩次的時間區域加入double_bookings。

最後，把新行程加入single_bookings，並且返回True，代表成功排入這個新行程。

程式碼 每個時間點最多允許兩個行程，拒絕第三個行程。

class MyCalendarTwo:
    def __init__(self):

        # 紀錄被一個行程佔據的時間區間
        self.single_bookings = []

        # 紀錄被兩個行程佔據的時間區間
        self.double_bookings = []

    def book(self, start: int, end: int) -> bool:
        # 檢查新行程是否有和兩個已知的行程重疊?
        # 如果有，直接拒絕新行程，返回 False。
        for double_start, double_end in self.double_bookings:
            if start < double_end and end > double_start:
                return False
        
        # 檢查新行程是否有和一個已知的行程重疊?
        # 如果有，把重疊的時間區域記錄下來，加入double booking。
        for single_start, single_end in self.single_bookings:
            if start < single_end and end > single_start:
                self.double_bookings.append((max(start, single_start), min(end, single_end)))
        
        # 接受當下這個新行程，返回True
        self.single_bookings.append((start, end))
        return True

複雜度分析

時間複雜度: O(n^2)

總共有n個行程，每個行程需要花費O(n)時間和已知行程做檢查。
總共耗時O(n^2)

空間複雜度: O(n)

需要額外建立兩張表格，single_bookings和 double_bookings，
所需空間皆為O(n)

關鍵知識點

考的是區間如何表達，以及新增區間，檢查區間有無重疊的演算法。

強烈建議讀著一併複習相關系列題，鞏固知識點。

📆行程安排 我的行事曆I_My Calendar I_Leetcode #729

Reference

[1] My Calendar II - LeetCode