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

《我的日程安排表》截止目前（2020-02-03）在 LeetCode 上一共有三道题，其中两个中等难度，一个困难难度,分别是：

另外 LeetCode 上有一个类似的系列《会议室》，截止目前（2020-02-03）有两道题目。其中一个简单一个中等，分别是：

今天我们就来攻克它们。

729. 我的日程安排表 I

题目地址

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

题目描述

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的时间内没有其他安排，则可以存储这个新的日程安排。

MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，即 [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 指的是日常安排的数量，对于每个新的日常安排，我们检查新的日常安排是否发生冲突来决定是否可以预订新的日常安排。
空间复杂度: $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

我们考虑使用平衡二叉树来维护这种动态的变化，在最差的情况时间复杂度会退化到上述的 $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 方法时，如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 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 节点增加一个字段的方式来标记，在这里我们使用 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 类来存放你的日程安排，你可以一直添加新的日程安排。

当 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 来存储所有的预定，对于每次插入，我们执行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。

读到这里，你可能会发现：这个解法似乎更具有通用型。对于第一题我们可以判断 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 上的专题《我的日程安排》的三道题进行了汇总。对于区间判断是否重叠，我们可以反向判断，也可以正向判断。暴力的方法是每次对所有的课程进行判断是否重叠，这种解法可以 AC。我们也可以进一步优化，使用二叉查找树来简化时间复杂度。最后我们介绍了一种 Count-Map 方法来通用解决所有的问题，不仅可以完美解决这三道题，还可以扩展到《会议室》系列的两道题。

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,293评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,604评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,958评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,729评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,719评论 5赞 366
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,630评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,000评论 3赞 397
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,665评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,909评论 1赞 299
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,646评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,726评论 1赞 330
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,400评论 4赞 321
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,986评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,959评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,197评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 44,996评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,481评论 2赞 342

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

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

729. 我的日程安排表 I

题目地址

题目描述

暴力法

思路

代码

二叉查找树法

思路

代码

731. 我的日程安排表 II

题目地址

题目描述

暴力法

思路

代码

二叉查找树法

代码

732. 我的日程安排表 III

题目地址

题目描述

二叉查找树法

思路

代码

Count Map 法

思路

代码

相关题目

总结

推荐阅读更多精彩内容