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

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

252. 會議室
253. 會議室 II

今天我們就來攻克它們。

729. 我的日程安排表 I

題目地址

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

題目描述

實(shí)現(xiàn)一個(gè) MyCalendar 類來存放你的日程安排。如果要添加的時(shí)間內(nèi)沒有其他安排，則可以存儲這個(gè)新的日程安排。

MyCalendar 有一個(gè) book(int start, int end)方法。它意味著在 start 到 end 時(shí)間內(nèi)增加一個(gè)日程安排，注意，這里的時(shí)間是半開區(qū)間，即 [start, end), 實(shí)數(shù) x 的范圍為， start <= x < end。

當(dāng)兩個(gè)日程安排有一些時(shí)間上的交叉時(shí)（例如兩個(gè)日程安排都在同一時(shí)間內(nèi)），就會產(chǎn)生重復(fù)預(yù)訂。

每次調(diào)用 MyCalendar.book 方法時(shí)，如果可以將日程安排成功添加到日歷中而不會導(dǎo)致重復(fù)預(yù)訂，返回 true。否則，返回 false 并且不要將該日程安排添加到日歷中。

請按照以下步驟調(diào)用 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
解釋:
第一個(gè)日程安排可以添加到日歷中. 第二個(gè)日程安排不能添加到日歷中，因?yàn)闀r(shí)間 15 已經(jīng)被第一個(gè)日程安排預(yù)定了。
第三個(gè)日程安排可以添加到日歷中，因?yàn)榈谝粋€(gè)日程安排并不包含時(shí)間 20 。
說明:

每個(gè)測試用例，調(diào)用 MyCalendar.book 函數(shù)最多不超過 100 次。
調(diào)用函數(shù) MyCalendar.book(start, end)時(shí)， start 和 end 的取值范圍為 [0, 10^9]。

暴力法

思路

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

我們定一個(gè)函數(shù)intersected(calendar, calendars)，其中 calendar 是即將要插入的課程，calendars 是已經(jīng)插入的課程。只要 calendar 和 calendars 中的任何一個(gè)課程有交叉，我們就返回 True，否則返回 False。

對于兩個(gè) calendar，我們的判斷邏輯都是一樣的。假設(shè)連個(gè) calendar 分別是[s1, e1]和[s2, e2]。那么如果s1 >= e2 or s2 <= e1, 則兩個(gè)課程沒有交叉，可以預(yù)定，否則不可以。如圖，1，2，3 可以預(yù)定，剩下的不可以。

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

復(fù)雜度分析：

時(shí)間復(fù)雜度： $O(N^2)$ 。N 指的是日常安排的數(shù)量，對于每個(gè)新的日常安排，我們檢查新的日常安排是否發(fā)生沖突來決定是否可以預(yù)訂新的日常安排。
空間復(fù)雜度: $O(N)$ 。

這個(gè)代碼寫出來之后整體代碼就呼之欲出了，全部代碼見下方代碼部分。

代碼

代碼支持 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

實(shí)際上我們還可以換個(gè)角度，上面的思路判斷交叉部分我們考慮的是“如何不交叉”，剩下的就是交叉。我們也可以直接考慮交叉。還是上面的例子，如果兩個(gè)課程交叉，那么一定滿足s1 < e2 and e1 > s2?；诖耍覀儗懗鱿旅娴拇a。

代碼支持 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 進(jìn)行排序，那么我們可以通過二分查找日程安排的情況來檢查新日常安排是否可以預(yù)訂。如果每次插入之前都進(jìn)行一次排序，那么時(shí)間復(fù)雜度會很高。如圖，我們的[s1,e1], [s2,e2], [s3,e3] 是按照時(shí)間順序排好的日程安排。我們現(xiàn)在要插入[s,e],我們使用二分查找，找到要插入的位置，然后和插入位置的課程進(jìn)行一次比對即可，這部分的時(shí)間復(fù)雜度是 O(logN)$。

image.png

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

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

題目描述

實(shí)現(xiàn)一個(gè) MyCalendar 類來存放你的日程安排。如果要添加的時(shí)間內(nèi)不會導(dǎo)致三重預(yù)訂時(shí)，則可以存儲這個(gè)新的日程安排。

當(dāng)三個(gè)日程安排有一些時(shí)間上的交叉時(shí)（例如三個(gè)日程安排都在同一時(shí)間內(nèi)），就會產(chǎn)生三重預(yù)訂。

每次調(diào)用 MyCalendar.book 方法時(shí)，如果可以將日程安排成功添加到日歷中而不會導(dǎo)致三重預(yù)訂，返回 true。否則，返回 false 并且不要將該日程安排添加到日歷中。

請按照以下步驟調(diào)用 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
解釋：
前兩個(gè)日程安排可以添加至日歷中。第三個(gè)日程安排會導(dǎo)致雙重預(yù)訂，但可以添加至日歷中。
第四個(gè)日程安排活動（5,15）不能添加至日歷中，因?yàn)樗鼤?dǎo)致三重預(yù)訂。
第五個(gè)日程安排（5,10）可以添加至日歷中，因?yàn)樗词褂靡呀?jīng)雙重預(yù)訂的時(shí)間 10。
第六個(gè)日程安排（25,55）可以添加至日歷中，因?yàn)闀r(shí)間 [25,40] 將和第三個(gè)日程安排雙重預(yù)訂；
時(shí)間 [40,50] 將單獨(dú)預(yù)訂，時(shí)間 [50,55）將和第二個(gè)日程安排雙重預(yù)訂。

提示：

每個(gè)測試用例，調(diào)用 MyCalendar.book 函數(shù)最多不超過 1000 次。
調(diào)用函數(shù) MyCalendar.book(start, end)時(shí)， start 和 end 的取值范圍為 [0, 10^9]。

暴力法

思路

暴力法和上述思路類似。但是我們多維護(hù)一個(gè)數(shù)組 intersectedCalendars 用來存儲二次預(yù)定的日程安排。如果課程第一次沖突，我們將其加入 intersectedCalendars，如果和 intersectedCalendars 也沖突了，說明出現(xiàn)了三次預(yù)定，我們直接返回 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

二叉查找樹法

和上面的題目類似，我們?nèi)匀豢梢允褂闷胶舛鏄鋪砗喕檎疫壿嫛＞唧w可以參考這個(gè) discussion

每次插入之前我們都需要進(jìn)行一次判斷，判斷是否可以插入。如果不可以插入，直接返回 False，否則我們進(jìn)行一次插入。插入的時(shí)候，如果和已有的相交了，我們判斷是否之前已經(jīng)相交了一次，如果是返回 False，否則返回 True。關(guān)于如何判斷是否和已有的相交，我們可以在 node 節(jié)點(diǎn)增加一個(gè)字段的方式來標(biāo)記，在這里我們使用 single_overlap，True 表示產(chǎn)生了二次預(yù)定，F(xiàn)alse 則表示沒有產(chǎn)生過兩次及以上的預(yù)定。

代碼

代碼支持 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/

題目描述

實(shí)現(xiàn)一個(gè) MyCalendar 類來存放你的日程安排，你可以一直添加新的日程安排。

當(dāng) K 個(gè)日程安排有一些時(shí)間上的交叉時(shí)（例如 K 個(gè)日程安排都在同一時(shí)間內(nèi)），就會產(chǎn)生 K 次預(yù)訂。

每次調(diào)用 MyCalendar.book 方法時(shí)，返回一個(gè)整數(shù) K ，表示最大的 K 次預(yù)訂。

請按照以下步驟調(diào)用 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
解釋:
前兩個(gè)日程安排可以預(yù)訂并且不相交，所以最大的 K 次預(yù)訂是 1。
第三個(gè)日程安排[10,40]與第一個(gè)日程安排相交，最高的 K 次預(yù)訂為 2。
其余的日程安排的最高 K 次預(yù)訂僅為 3。
請注意，最后一次日程安排可能會導(dǎo)致局部最高 K 次預(yù)訂為 2，但答案仍然是 3，原因是從開始到最后，時(shí)間[10,20]，[10,40]和[5,15]仍然會導(dǎo)致 3 次預(yù)訂。
說明:

每個(gè)測試用例，調(diào)用 MyCalendar.book 函數(shù)最多不超過 400 次。
調(diào)用函數(shù) MyCalendar.book(start, end)時(shí)， start 和 end 的取值范圍為 [0, 10^9]。

二叉查找樹法

思路

我們?nèi)匀豢梢允褂蒙鲜龅钠胶舛鏄涞淖龇?。只不過我們需要額外維護(hù)一個(gè)全局的最大值“k”，表示需要多少個(gè)預(yù)定。最終我們返回 k。同時(shí)每一個(gè) node 我們都增加一個(gè)屬性 k，用來表示局部的最大值，對于每次插入，我們將 node 的 k 和全部的 k 進(jìn)行比較，取出最大值即可。

代碼

代碼支持 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 法

思路

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

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

比如預(yù)定[1,3]和[5,7]，我們產(chǎn)生一個(gè)預(yù)定即可：

image.png

再比如預(yù)定[1,5]和[3,7]，我們需要兩個(gè)預(yù)定：

image.png

我們可以使用紅黑樹來簡化時(shí)間復(fù)雜度，如果你使用的是 Java，可以直接使用現(xiàn)成的數(shù)據(jù)結(jié)構(gòu) TreeMap。我這里偷懶，每次都排序，時(shí)間復(fù)雜度會很高，但是可以 AC。

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

如果你不借助紅黑樹等數(shù)據(jù)結(jié)構(gòu)直接使用 count-map 法，即每次都進(jìn)行一次排序，第一題和第二題可能會直接超時(shí)。

代碼

代碼支持 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)

總結(jié)

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

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

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

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

729. 我的日程安排表 I

題目地址

題目描述

暴力法

思路

代碼

二叉查找樹法

思路

代碼

731. 我的日程安排表 II

題目地址

題目描述

暴力法

思路

代碼

二叉查找樹法

代碼

732. 我的日程安排表 III

題目地址

題目描述

二叉查找樹法

思路

代碼

Count Map 法

思路

代碼

相關(guān)題目

總結(jié)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

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

729. 我的日程安排表 I

題目地址

題目描述

暴力法

思路

代碼

二叉查找樹法

思路

代碼

731. 我的日程安排表 II

題目地址

題目描述

暴力法

思路

代碼

二叉查找樹法

代碼

732. 我的日程安排表 III

題目地址

題目描述

二叉查找樹法

思路

代碼

Count Map 法

思路

代碼

相關(guān)題目

總結(jié)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av