我的日程安排表 II

难度: Medium

实现一个 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)

示例：

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]。

Submission

运行时间: 180 ms

内存: 0.0 MB

class MyCalendarTwo:

    def __init__(self):
        
        self.ss, self.ee = [], []
    def book(self, start: int, end: int) -> bool:
        ind1, ind2 = bisect.bisect_right(self.ee, start), bisect.bisect_left(self.ss, end)
        for ii in range(ind1, ind2-1):
            if self.ee[ii]>self.ss[ii+1]: return False
        bisect.insort(self.ss, start)
        bisect.insort(self.ee, end)
        return True

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

Explain

这个题解使用了有序列表来维护当前已预订的日程安排的开始和结束时间。当要预订一个新的日程时，首先用二分查找找到新日程的开始时间在结束时间列表中的位置ind1，以及结束时间在开始时间列表中的位置ind2。然后检查ind1到ind2-1范围内的日程，看是否会产生三重预订（即某个已有日程的结束时间大于下一个日程的开始时间）。如果不会导致三重预订，就将新日程的开始和结束时间分别插入到开始时间列表和结束时间列表的合适位置。

时间复杂度: O(n)

空间复杂度: O(n)

class MyCalendarTwo:

    def __init__(self):
        # 初始化存储所有日程开始时间的列表
        self.ss = []
        # 初始化存储所有日程结束时间的列表 
        self.ee = []
        
    def book(self, start: int, end: int) -> bool:
        # 找到新日程开始时间在结束时间列表中的位置
        ind1 = bisect.bisect_right(self.ee, start)
        # 找到新日程结束时间在开始时间列表中的位置
        ind2 = bisect.bisect_left(self.ss, end)
        # 检查 ind1 到 ind2-1 范围内的已有日程
        for ii in range(ind1, ind2-1):
            # 如果某个日程的结束时间大于下一个日程的开始时间，说明会产生三重预订
            if self.ee[ii] > self.ss[ii+1]:
                return False
        # 将新日程的开始时间插入到开始时间列表的合适位置    
        bisect.insort(self.ss, start)
        # 将新日程的结束时间插入到结束时间列表的合适位置
        bisect.insort(self.ee, end)
        return True

Explore

在题解中，二分查找用于确定新日程的开始时间和结束时间应插入的位置。通过找到这两个位置，可以确定新日程与现有日程的重叠部分。具体来说，ind1是新日程开始时间应该插入的位置，表示所有结束时间小于或等于新日程开始时间的日程都不会与新日程重叠。同理，ind2是新日程结束时间应该插入的位置，表示所有开始时间大于或等于新日程结束时间的日程也不会与新日程重叠。因此，只需要检查从ind1到ind2-1的日程，这些是可能与新日程重叠的日程。如果在这个范围内的任何已有日程的结束时间大于下一个日程的开始时间，意味着存在至少三个日程在某个时间点重叠，从而导致三重预订。

检查从ind1到ind2-1的范围是因为这些位置表示的日程是新日程可能会直接影响的日程，即这些日程的结束时间在新日程的开始时间之后，且开始时间在新日程的结束时间之前。这样的日程表示它们与新日程有时间上的重叠。在这个范围之外的日程，要么完全在新日程开始之前结束，要么开始于新日程结束之后，因此不会与新日程产生直接的时间重叠。因此，这个范围确实能够覆盖所有可能与新日程产生三重预订的情况。

最坏的情况出现在新日程的时间范围非常广泛，以至于它可能与所有已有的日程重叠。例如，如果一个新日程的开始时间非常早，结束时间非常晚，那么新日程的时间范围可能覆盖所有或大部分已有日程。在这种情况下，由于ind1很小（接近0），而ind2很大（接近已有日程数量），检查是否产生三重预订的循环需要遍历从ind1到ind2-1的所有日程，即几乎是所有已有的日程，这就是最坏的情况。