【算法提高班】《我的日程安排表》系列

《我的日程安排表》截止目前（2020-02-03）在 LeetCode 上一共有三道題，其中兩個中等難度，一個困難難度,分別是：

729. 我的日程安排表 I
731. 我的日程安排表 II
732. 我的日程安排表 III

另外 LeetCode 上有一個類似的系列《會議室》，截止目前（2020-02-03）有兩道題目。其中一個簡單一個中等，分別是：

252. 會議室
253. 會議室 II

今天我們就來攻克它們贴届。

729. 我的日程安排表 I

題目地址

https://leetcode-cn.com/problems/my-calendar-i

題目描述

實現一個 MyCalendar 類來存放你的日程安排。如果要添加的時間內沒有其他安排蜡吧，則可以存儲這個新的日程安排毫蚓。

MyCalendar 有一個 book(int start, int end)方法。它意味著在 start 到 end 時間內增加一個日程安排昔善，注意元潘，這里的時間是半開區(qū)間，即 [start, end), 實數 x 的范圍為耀鸦， start <= x < end柬批。

當兩個日程安排有一些時間上的交叉時（例如兩個日程安排都在同一時間內）啸澡，就會產生重復預訂袖订。

每次調用 MyCalendar.book 方法時，如果可以將日程安排成功添加到日歷中而不會導致重復預訂嗅虏，返回 true洛姑。否則，返回 false 并且不要將該日程安排添加到日歷中皮服。

請按照以下步驟調用 MyCalendar 類: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

示例 1:

MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(15, 25); // returns false
MyCalendar.book(20, 30); // returns true
解釋:
第一個日程安排可以添加到日歷中. 第二個日程安排不能添加到日歷中楞艾，因為時間 15 已經被第一個日程安排預定了参咙。
第三個日程安排可以添加到日歷中，因為第一個日程安排并不包含時間 20 硫眯。
說明:

每個測試用例蕴侧，調用 MyCalendar.book 函數最多不超過 100 次。
調用函數 MyCalendar.book(start, end)時两入， start 和 end 的取值范圍為 [0, 10^9]净宵。

暴力法

思路

首先我們考慮暴力法。每插入一個元素我們都判斷其是否和已有的所有課程重疊裹纳。

我們定一個函數intersected(calendar, calendars)择葡，其中 calendar 是即將要插入的課程，calendars 是已經插入的課程剃氧。只要 calendar 和 calendars 中的任何一個課程有交叉敏储，我們就返回 True，否則返回 False朋鞍。

對于兩個 calendar已添，我們的判斷邏輯都是一樣的。假設連個 calendar 分別是[s1, e1]和[s2, e2]滥酥。那么如果s1 >= e2 or s2 <= e1, 則兩個課程沒有交叉酝碳，可以預定，否則不可以恨狈。如圖疏哗，1，2禾怠，3 可以預定返奉，剩下的不可以。

image.png

代碼是這樣的：

    def intersected(calendar, calendars):
        for [start, end] in calendars:
            if calendar[0] >= end or calendar[1] <= start:
                continue
            else:
                return True

        return False

復雜度分析：

時間復雜度： $O(N^2)$ 吗氏。N 指的是日常安排的數量芽偏，對于每個新的日常安排，我們檢查新的日常安排是否發(fā)生沖突來決定是否可以預訂新的日常安排弦讽。
空間復雜度: $O(N)$ 污尉。

這個代碼寫出來之后整體代碼就呼之欲出了，全部代碼見下方代碼部分往产。

代碼

代碼支持 Python3:

Python3 Code:

#
# @lc app=leetcode.cn id=729 lang=python3
#
# [729] 我的日程安排表 I
#

# @lc code=start


class MyCalendar:

    def __init__(self):
        self.calendars = []

    def book(self, start: int, end: int) -> bool:
        def intersected(calendar, calendars):
            for [start, end] in calendars:
                if calendar[0] >= end or calendar[1] <= start:
                    continue
                else:
                    return True

            return False
        if intersected([start, end], self.calendars):
            return False
        self.calendars.append([start, end])
        return True

        # Your MyCalendar object will be instantiated and called as such:
        # obj = MyCalendar()
        # param_1 = obj.book(start,end)
        # @lc code=end

實際上我們還可以換個角度被碗，上面的思路判斷交叉部分我們考慮的是“如何不交叉”，剩下的就是交叉仿村。我們也可以直接考慮交叉锐朴。還是上面的例子，如果兩個課程交叉蔼囊，那么一定滿足s1 < e2 and e1 > s2焚志∫旅裕基于此，我們寫出下面的代碼酱酬。

代碼支持 Python3:

Python3 Code:

#
# @lc app=leetcode.cn id=729 lang=python3
#
# [729] 我的日程安排表 I
#

# @lc code=start


class MyCalendar:

    def __init__(self):
        self.calendars = []

    def book(self, start: int, end: int) -> bool:
        for s, e in self.calendars:
            if start < e and end > s:
                return False
        self.calendars.append([start, end])
        return True

        # Your MyCalendar object will be instantiated and called as such:
        # obj = MyCalendar()
        # param_1 = obj.book(start,end)
        # @lc code=end

二叉查找樹法

思路

和上面思路類似壶谒，只不過我們每次都對 calendars 進行排序，那么我們可以通過二分查找日程安排的情況來檢查新日常安排是否可以預訂膳沽。如果每次插入之前都進行一次排序佃迄，那么時間復雜度會很高。如圖贵少，我們的[s1,e1], [s2,e2], [s3,e3] 是按照時間順序排好的日程安排呵俏。我們現在要插入[s,e],我們使用二分查找，找到要插入的位置滔灶，然后和插入位置的課程進行一次比對即可普碎，這部分的時間復雜度是 O(logN)$。

image.png

我們考慮使用平衡二叉樹來維護這種動態(tài)的變化录平，在最差的情況時間復雜度會退化到上述的 $O(N^2)$ 麻车，平均情況是 $O(NlogN)$ ，其中 N 是已預訂的日常安排數斗这。

image.png

代碼

代碼支持 Python3:

Python3 Code:

class Node:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.left = self.right = None

    def insert(self, node):
        if node.start >= self.end:
            if not self.right:
                self.right = node
                return True
            return self.right.insert(node)
        elif node.end <= self.start:
            if not self.left:
                self.left = node
                return True
            return self.left.insert(node)
        else:
            return False

class MyCalendar(object):
    def __init__(self):
        self.root = None

    def book(self, start, end):
        if self.root is None:
            self.root = Node(start, end)
            return True
        return self.root.insert(Node(start, end))

731. 我的日程安排表 II

題目地址

https://leetcode-cn.com/problems/my-calendar-ii

題目描述

實現一個 MyCalendar 類來存放你的日程安排动猬。如果要添加的時間內不會導致三重預訂時表箭，則可以存儲這個新的日程安排。

MyCalendar 有一個 book(int start, int end)方法彼水。它意味著在 start 到 end 時間內增加一個日程安排，注意凤覆，這里的時間是半開區(qū)間拆魏，即 [start, end), 實數 x 的范圍為盯桦， start <= x < end拥峦。

當三個日程安排有一些時間上的交叉時（例如三個日程安排都在同一時間內）步鉴，就會產生三重預訂璃哟。

每次調用 MyCalendar.book 方法時，如果可以將日程安排成功添加到日歷中而不會導致三重預訂铐伴，返回 true当宴。否則，返回 false 并且不要將該日程安排添加到日歷中梯浪。

請按照以下步驟調用 MyCalendar 類: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

示例：

MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(50, 60); // returns true
MyCalendar.book(10, 40); // returns true
MyCalendar.book(5, 15); // returns false
MyCalendar.book(5, 10); // returns true
MyCalendar.book(25, 55); // returns true
解釋：
前兩個日程安排可以添加至日歷中。第三個日程安排會導致雙重預訂虏劲，但可以添加至日歷中伙单。
第四個日程安排活動（5,15）不能添加至日歷中，因為它會導致三重預訂布疼。
第五個日程安排（5,10）可以添加至日歷中游两，因為它未使用已經雙重預訂的時間 10。
第六個日程安排（25,55）可以添加至日歷中宝踪，因為時間 [25,40] 將和第三個日程安排雙重預訂瘩燥；
時間 [40,50] 將單獨預訂溶耘，時間 [50,55）將和第二個日程安排雙重預訂凳兵。

提示：

每個測試用例，調用 MyCalendar.book 函數最多不超過 1000 次聚蝶。
調用函數 MyCalendar.book(start, end)時碘勉， start 和 end 的取值范圍為 [0, 10^9]。

暴力法

思路

暴力法和上述思路類似胜嗓。但是我們多維護一個數組 intersectedCalendars 用來存儲二次預定的日程安排。如果課程第一次沖突变过，我們將其加入 intersectedCalendars媚狰，如果和 intersectedCalendars 也沖突了，說明出現了三次預定辨宠，我們直接返回 False黄伊。

代碼

代碼支持 Python3:

Python3 Code:

class MyCalendarTwo:

    def __init__(self):
        self.calendars = []
        self.intersectedCalendars = []

    def book(self, start: int, end: int) -> bool:
        for [s, e] in self.intersectedCalendars:
            if start < e and end > s:
                return False
        for [s, e] in self.calendars:
            if start < e and end > s:
                self.intersectedCalendars.append([max(start, s), min(end, e)])
        self.calendars.append([start, end])
        return True

二叉查找樹法

和上面的題目類似墓阀，我們仍然可以使用平衡二叉樹來簡化查找邏輯斯撮。具體可以參考這個 discussion

每次插入之前我們都需要進行一次判斷帕膜，判斷是否可以插入垮刹。如果不可以插入，直接返回 False寺董，否則我們進行一次插入遮咖。插入的時候，如果和已有的相交了魄藕，我們判斷是否之前已經相交了一次，如果是返回 False寝姿，否則返回 True埃篓。關于如何判斷是否和已有的相交架专，我們可以在 node 節(jié)點增加一個字段的方式來標記，在這里我們使用 single_overlap委刘，True 表示產生了二次預定，False 則表示沒有產生過兩次及以上的預定淆珊。

代碼

代碼支持 Python3:

Python3 Code:

class Node:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.left = None
        self.right = None
        self.single_overlap = False

class MyCalendarTwo:

    def __init__(self):
        self.root = None

    def book(self, start, end):
        if not self.canInsert(start, end, self.root):
            return False

        self.root = self.insert(start, end, self.root)
        return True


    def canInsert(self, start, end, root):
        if not root:
            return True

        if start >= end:
            return True

        if end <= root.start:
            return self.canInsert(start, end, root.left)

        elif start >= root.end:
            return self.canInsert(start, end, root.right)

        else:
            if root.single_overlap:
                return False
            elif start >= root.start and end <= root.end:
                return True
            else:
                return self.canInsert(start, root.start, root.left) and self.canInsert(root.end, end, root.right)



    def insert(self, start, end, root):
        if not root:
            root = Node(start, end)
            return root

        if start >= end:
            return root

        if start >= root.end:
            root.right = self.insert(start, end, root.right)

        elif end <= root.start:
            root.left = self.insert(start, end, root.left)

        else:
            root.single_overlap = True
            a = min(root.start, start)
            b = max(root.start, start)
            c = min(root.end, end)
            d = max(root.end, end)
            root.start, root.end = b, c
            root.left, root.right = self.insert(a, b, root.left), self.insert(c, d, root.right)

        return root

# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(start,end)

732. 我的日程安排表 III

題目地址

https://leetcode-cn.com/problems/my-calendar-iii/

題目描述

實現一個 MyCalendar 類來存放你的日程安排操刀，你可以一直添加新的日程安排骨坑。

MyCalendar 有一個 book(int start, int end)方法。它意味著在 start 到 end 時間內增加一個日程安排礁遣，注意杏头，這里的時間是半開區(qū)間醇王，即 [start, end), 實數 x 的范圍為， start <= x < end棘伴。

當 K 個日程安排有一些時間上的交叉時（例如 K 個日程安排都在同一時間內）畸裳，就會產生 K 次預訂帅容。

每次調用 MyCalendar.book 方法時并徘，返回一個整數 K ，表示最大的 K 次預訂姐直。

請按照以下步驟調用 MyCalendar 類: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

示例 1:

MyCalendarThree();
MyCalendarThree.book(10, 20); // returns 1
MyCalendarThree.book(50, 60); // returns 1
MyCalendarThree.book(10, 40); // returns 2
MyCalendarThree.book(5, 15); // returns 3
MyCalendarThree.book(5, 10); // returns 3
MyCalendarThree.book(25, 55); // returns 3
解釋:
前兩個日程安排可以預訂并且不相交姻成，所以最大的 K 次預訂是 1科展。
第三個日程安排[10,40]與第一個日程安排相交徘跪，最高的 K 次預訂為 2鹃答。
其余的日程安排的最高 K 次預訂僅為 3测摔。
請注意，最后一次日程安排可能會導致局部最高 K 次預訂為 2挟纱，但答案仍然是 3，原因是從開始到最后欺嗤，時間[10,20]，[10,40]和[5,15]仍然會導致 3 次預訂吆玖。
說明:

每個測試用例沾乘，調用 MyCalendar.book 函數最多不超過 400 次。
調用函數 MyCalendar.book(start, end)時， start 和 end 的取值范圍為 [0, 10^9]槐雾。

二叉查找樹法

思路

我們仍然可以使用上述的平衡二叉樹的做法株灸。只不過我們需要額外維護一個全局的最大值“k”，表示需要多少個預定。最終我們返回 k。同時每一個 node 我們都增加一個屬性 k，用來表示局部的最大值，對于每次插入芹壕，我們將 node 的 k 和全部的 k 進行比較船殉，取出最大值即可挨厚。

代碼

代碼支持 Python3:

Python3 Code:


class Node(object):
    def __init__(self, start, end, ktime=1):
        self.k = ktime
        self.s = start
        self.e = end
        self.right = None
        self.left = None

class MyCalendarThree(object):

    def __init__(self):
        self.root = None
        self.k = 0

    def book(self, start, end):
        self.root = self.insert(self.root, start, end, 1)
        return self.k
    def insert(self, root, start, end, k):
        if start >= end:
            return root
        if not root:
            self.k = max(self.k, k)
            return Node(start, end, k)
        else:
            if start >= root.e:
                root.right = self.insert(root.right, start, end, k)
                return root
            elif end <= root.s:
                root.left = self.insert(root.left, start, end, k)
                return root
            else:

                a = min(root.s, start)
                b = max(root.s, start)
                c = min(root.e, end)
                d = max(root.e, end)

                root.left = self.insert(root.left, a, b, a == root.s and root.k or k)
                root.right = self.insert(root.right, c,d, d == root.e and root.k or k)
                root.k += k
                root.s = b
                root.e = c
                self.k = max(root.k, self.k)
                return root

Count Map 法

思路

這個是我在看了 Discussion [C++] Map Solution, beats 95%+ 之后寫的解法巢价，解法非常巧妙。

我們使用一個 count map 來存儲所有的預定碉克，對于每次插入客税，我們執(zhí)行count[start] += 1和count[end] -= 1。 count[t] 表示從 t 開始到下一個 t 我們有幾個預定酥夭。因此我們需要對 count 進行排序才行。我們維護一個最大值來 cnt 來表示需要的預定數。

比如預定[1,3]和[5,7]巫延，我們產生一個預定即可：

image.png

再比如預定[1,5]和[3,7]脉执，我們需要兩個預定：

image.png

我們可以使用紅黑樹來簡化時間復雜度，如果你使用的是 Java淘邻，可以直接使用現成的數據結構 TreeMap。我這里偷懶，每次都排序崎溃，時間復雜度會很高概而，但是可以 AC。

讀到這里餐曼，你可能會發(fā)現：這個解法似乎更具有通用型。對于第一題我們可以判斷 cnt 是否小于等于 1，對于第二題我們可以判斷 cnt 是否小于等于 2养渴。

如果你不借助紅黑樹等數據結構直接使用 count-map 法，即每次都進行一次排序，第一題和第二題可能會直接超時孵滞。

代碼

代碼支持 Python3:

Python3 Code:

class MyCalendarThree:

    def __init__(self):
        self.count = dict()

    def book(self, start: int, end: int) -> int:
        self.count[start] = self.count.get(start, 0) + 1
        self.count[end] = self.count.get(end, 0) - 1
        cnt = 0
        cur = 0

        for k in sorted(self.count):
            cur += self.count[k]
            cnt = max(cnt, cur)
        return cnt

        # Your MyCalendarThree object will be instantiated and called as such:
        # obj = MyCalendarThree()
        # param_1 = obj.book(start,end)

總結

我們對 LeetCode 上的專題《我的日程安排》的三道題進行了匯總染厅。對于區(qū)間判斷是否重疊痘绎，我們可以反向判斷，也可以正向判斷肖粮。暴力的方法是每次對所有的課程進行判斷是否重疊孤页，這種解法可以 AC。我們也可以進一步優(yōu)化涩馆，使用二叉查找樹來簡化時間復雜度行施。最后我們介紹了一種 Count-Map 方法來通用解決所有的問題允坚，不僅可以完美解決這三道題，還可以擴展到《會議室》系列的兩道題蛾号。

?著作權歸作者所有,轉載或內容合作請聯系作者

人面猴
序言：七十年代末稠项，一起剝皮案震驚了整個濱河市，隨后出現的幾起案子鲜结，更是在濱河造成了極大的恐慌展运，老刑警劉巖，帶你破解...
沈念sama閱讀 218,858評論 6贊 508
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件精刷，死亡現場離奇詭異拗胜，居然都是意外死亡，警方通過查閱死者的電腦和手機怒允，發(fā)現死者居然都...
沈念sama閱讀 93,372評論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門挤土，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人误算，你說我怎么就攤上這事仰美。” “怎么了儿礼？”我有些...
開封第一講書人閱讀 165,282評論 0贊 356
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵咖杂，是天一觀的道長。經常有香客問我蚊夫，道長诉字，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 58,842評論 1贊 295
?港島之戀（遺憾婚禮）
正文為了忘掉前任知纷，我火速辦了婚禮壤圃，結果婚禮上，老公的妹妹穿的比我還像新娘琅轧。我一直安慰自己伍绳，他們只是感情好，可當我...
茶點故事閱讀 67,857評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布乍桂。她就那樣靜靜地躺著冲杀，像睡著了一般。火紅的嫁衣襯著肌膚如雪睹酌。梳的紋絲不亂的頭發(fā)上权谁，一...
開封第一講書人閱讀 51,679評論 1贊 305
城市分裂傳說
那天，我揣著相機與錄音憋沿，去河邊找鬼旺芽。笑死，一個胖子當著我的面吹牛，可吹牛的內容都是我干的采章。我是一名探鬼主播运嗜，決...
沈念sama閱讀 40,406評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼共缕！你這毒婦竟也來了洗出？” 一聲冷哼從身側響起，我...
開封第一講書人閱讀 39,311評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤图谷，失蹤者是張志新（化名）和其女友劉穎翩活，沒想到半個月后，有當地人在樹林里發(fā)現了一具尸體便贵，經...
沈念sama閱讀 45,767評論 1贊 315
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡菠镇，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內容為張勛視角年9月15日...
茶點故事閱讀 37,945評論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時候發(fā)現自己被綠了承璃。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片利耍。...
茶點故事閱讀 40,090評論 1贊 350
活死人
序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖盔粹，靈堂內的尸體忽然破棺而出隘梨，到底是詐尸還是另有隱情，我是刑警寧澤舷嗡，帶...
沈念sama閱讀 35,785評論 5贊 346
?日本核電站爆炸內幕
正文年R本政府宣布轴猎，位于F島的核電站，受9級特大地震影響进萄，放射性物質發(fā)生泄漏捻脖。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點故事閱讀 41,420評論 3贊 331
男人毒藥：我在死后第九天來索命
文/蒙蒙一中鼠、第九天我趴在偏房一處隱蔽的房頂上張望可婶。院中可真熱鬧，春花似錦援雇、人聲如沸矛渴。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,988評論 0贊 22
一樁弒父案熊杨，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽曙旭。三九已至，卻和暖如春晶府，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背钻趋。一陣腳步聲響...
開封第一講書人閱讀 33,101評論 1贊 271
情欲美人皮
我被黑心中介騙來泰國打工川陆，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人蛮位。一個月前我還...
沈念sama閱讀 48,298評論 3贊 372
代替公主和親
正文我出身青樓较沪，卻偏偏與公主長得像鳞绕，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子尸曼，可洞房花燭夜當晚...
茶點故事閱讀 45,033評論 2贊 355

【算法提高班】《我的日程安排表》系列

【算法提高班】《我的日程安排表》系列

729. 我的日程安排表 I

題目地址

題目描述

暴力法

思路

代碼

二叉查找樹法

思路

代碼

731. 我的日程安排表 II

題目地址

題目描述

暴力法

思路

代碼

二叉查找樹法

代碼

732. 我的日程安排表 III

題目地址

題目描述

二叉查找樹法

思路

代碼

Count Map 法

思路

代碼

相關題目

總結

推薦閱讀更多精彩內容