python⽇程表代码_【算法提⾼班】《我的⽇程安排表》系列《我的⽇程安排表》截⽌⽬前(2020-02-03)在 LeetCode 上⼀共有三道题，其中两个中等难度，⼀个困难难度，分别是：
另外 LeetCode 上有⼀个类似的系列《会议室》，截⽌⽬前(2020-02-03)有两道题⽬。其中⼀个简单⼀个中等，分别是：
今天我们就来攻克它们。
729. 我的⽇程安排表 I
题⽬地址
题⽬描述
实现⼀个 MyCalendar 类来存放你的⽇程安排。如果要添加的时间内没有其他安排，则可以存储这个新的⽇程安排。
MyCalendar 有⼀个 book(int start, int end)⽅法。它意味着在 start 到 end 时间内增加⼀个⽇程安排，注意，这⾥的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end。
当两个⽇程安排有⼀些时间上的交叉时(例如两个⽇程安排都在同⼀时间内)，就会产⽣重复预订。
每次调⽤ MyCalendar.book ⽅法时，如果可以将⽇程安排成功添加到⽇历中⽽不会导致重复预订，返回 true。否则，返回 fal 并且不要将该⽇程安排添加到⽇历中。
请按照以下步骤调⽤ MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)
⽰例 1:
MyCalendar(); MyCalendar.book(10, 20); // returns true MyCalendar.book(15, 25); // returns fal MyCalendar.book(20, 30); // returns true 解释: 第⼀个⽇程安排可以添加到⽇历中. 第⼆个⽇程安排不能添加到⽇历中，因为时间 15 已经被第⼀个⽇程安排预定了。 第三个⽇程安排可以添加到⽇历中，因为第⼀个⽇程安排并不包含时间 20 。 说明:
每个测试⽤例，调⽤ MyCalendar.book 函数最多不超过 100 次。 调⽤函数 MyCalendar.book(start, end)时， start 和 end 的取值范围为 [0, 10^9]。
拜登 特朗普年龄暴⼒法
思路
⾸先我们考虑暴⼒法。每插⼊⼀个元素我们都判断其是否和已有的所有课程重叠。
我们定⼀个函数intercted(calendar, calendars)，其中 calendar 是即将要插⼊的课程，calendars 是已经插⼊的课程。 只要calendar 和 calendars 中的任何⼀个课程有交叉，我们就返回 True，否则返回 Fal。
对于两个 calendar，我们的判断逻辑都是⼀样的。假设连个 calendar 分别是[s1, e1]和[s2, e2]。那么如果s1 >= e2 or s2 <= e1, 则两个课程没有交叉，可以预定，否则不可以。如图，1，2，3 可以预定，剩下的不可以。
代码是这样的：
def intercted(calendar, calendars):
for [start, end] in calendars:
if calendar[0] >= end or calendar[1] <= start:
continue
el:
return True
return Fal
复杂度分析：时间复杂度：
。N 指的是⽇常安排的数量，对于每个新的⽇常安排，我们检查新的⽇常安排是否发⽣冲突来决定是否可以预订新的⽇常安排。
空间复杂度:
。
这个代码写出来之后整体代码就呼之欲出了，全部代码见下⽅代码部分。
代码
代码⽀持 Python3:
Python3 Code:
#
# @lc app=leetcode id=729 lang=python3
#
# [729] 我的⽇程安排表 I
#
# @lc code=start
class MyCalendar:
def __init__(lf):
lf.calendars = []
def book(lf, start: int, end: int) -> bool:
def intercted(calendar, calendars):
for [start, end] in calendars:
if calendar[0] >= end or calendar[1] <= start:
continue
el:
return True
return Fal
if intercted([start, end], lf.calendars):
return Fal
lf.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 id=729 lang=python3
#
# [729] 我的⽇程安排表 I
#
# @lc code=start
class MyCalendar:
def __init__(lf):
lf.calendars = []
def book(lf, start: int, end: int) -> bool:
for s, e in lf.calendars:
if start < e and end > s:
return Fal
lf.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)$。
我们考虑使⽤平衡⼆叉树来维护这种动态的变化，在最差的情况时间复杂度会退化到上述的
，平均情况是
，其中 N 是已预订的⽇常安排数。
网上英语一对一辅导代码
代码⽀持 Python3:
Python3 Code:
class Node:
def __init__(lf, start, end):
lf.start = start
lf.left = lf.right = None
def inrt(lf, node):
if node.start >= lf.end:
if not lf.right:
lf.right = node
return True
return lf.right.inrt(node)
d <= lf.start:
if not lf.left:
lf.left = node
return True
return lf.left.inrt(node)
el:
return Fal
class MyCalendar(object):
def __init__(lf):
< = None
def book(lf, start, end):
is None:
< = Node(start, end)
return True
inrt(Node(start, end))
731. 我的⽇程安排表 II
题⽬地址
grandpa题⽬描述
实现⼀个 MyCalendar 类来存放你的⽇程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的⽇程安排。
洋服
MyCalendar 有⼀个 book(int start, int end)⽅法。它意味着在 start 到 end 时间内增加⼀个⽇程安排，注意，这⾥的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end。
当三个⽇程安排有⼀些时间上的交叉时(例如三个⽇程安排都在同⼀时间内)，就会产⽣三重预订。
每次调⽤ MyCalendar.book ⽅法时，如果可以将⽇程安排成功添加到⽇历中⽽不会导致三重预订，返回 true。否则，返回 fal 并且不要将该⽇程安排添加到⽇历中。
请按照以下步骤调⽤ 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 fal 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]。
暴⼒法
思路
暴⼒法和上述思路类似。但是我们多维护⼀个数组 interctedCalendars ⽤来存储⼆次预定的⽇程安排。如果课程第⼀次冲突，我们将其加⼊ interctedCalendars，如果和 interctedCalendars 也冲突了，说明出现了三次预定，我们直接返回 Fal。
wen代码
代码⽀持 Python3:
Python3 Code:
i lone you是什么意思class MyCalendarTwo:
clk
allegorical
def __init__(lf):
lf.calendars = []
lf.interctedCalendars = []
英语宾语从句讲解
def book(lf, start: int, end: int) -> bool:
for [s, e] in lf.interctedCalendars:
if start < e and end > s:
return Fal
for [s, e] in lf.calendars:
if start < e and end > s:
lf.interctedCalendars.append([max(start, s), min(end, e)])
lf.calendars.append([start, end])
return True
⼆叉查找树法
和上⾯的题⽬类似，我们仍然可以使⽤平衡⼆叉树来简化查找逻辑。具体可以参考
每次插⼊之前我们都需要进⾏⼀次判断，判断是否可以插⼊。如果不可以插⼊，直接返回 Fal，否则我们进⾏⼀次插⼊。 插⼊的时候，如果和已有的相交了，我们判断是否之前已经相交了⼀次，如果是返回 Fal，否则返回 True。关于如何判断是否和已有的相交，我们可以在 node 节点增加⼀个字段的⽅式来标记，在这⾥我们使⽤ single_overlap，True 表⽰产⽣了⼆次预定，Fal 则表⽰没有产⽣过两次及以上的预定。
代码
代码⽀持 Python3:
Python3 Code:
