我的日程安排表 I

难度: Medium

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会造成 重复预订 ，则可以存储这个新的日程安排。

当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生 重复预订 。

日程可以用一对整数 start 和 end 表示，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end 。

实现 MyCalendar 类：

MyCalendar() 初始化日历对象。
boolean book(int start, int end) 如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 true 。否则，返回 false 并且不要将该日程安排添加到日历中。

示例：

输入：
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
输出：
[null, true, false, true]

解释：
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False ，这个日程安排不能添加到日历中，因为时间 15 已经被另一个日程安排预订了。
myCalendar.book(20, 30); // return True ，这个日程安排可以添加到日历中，因为第一个日程安排预订的每个时间都小于 20 ，且不包含时间 20 。

提示：

0 <= start < end <= 10⁹
每个测试用例，调用 book 方法的次数最多不超过 1000 次。

Submission

运行时间: 121 ms

内存: 16.9 MB

class MyCalendar:

    def __init__(self):
        self.starts = []
        self.ends = {}

    def book(self, start: int, end: int) -> bool:
        i = bisect_right(self.starts, start)
        if i>0:
            if self.starts[i-1] == start:
                return False
            if self.ends[self.starts[i-1]] > start:
                return False
            if i < len(self.starts) and self.starts[i] < end:
                return False
        else:
            if self.starts and end > self.starts[0]:
                return False
        self.starts.insert(i, start)
        self.ends[start] = end
        return True


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

Explain

该题解使用两个数组 starts 和 ends 来分别存储每个日程的开始时间和结束时间。当需要添加新的日程时，使用二分查找来找到 starts 数组中第一个大于等于新日程开始时间的位置 i。然后进行以下检查： 1. 如果 i>0 且 starts[i-1] 等于新日程的开始时间，说明存在重复预订，返回 False。 2. 如果 i>0 且前一个日程的结束时间大于新日程的开始时间，说明存在重复预订，返回 False。 3. 如果 i<len(starts) 且下一个日程的开始时间小于新日程的结束时间，说明存在重复预订，返回 False。 4. 如果 i==0 且 starts 不为空，且新日程的结束时间大于 starts[0]，说明存在重复预订，返回 False。如果以上检查都通过，则将新日程的开始时间插入到 starts[i] 的位置，并在 ends 中记录其对应的结束时间，最后返回 True 表示成功添加日程。

时间复杂度: O(n)

空间复杂度: O(n)

class MyCalendar:

    def __init__(self):
        self.starts = []  # 存储日程的开始时间
        self.ends = {}    # 存储日程的结束时间

    def book(self, start: int, end: int) -> bool:
        # 使用二分查找找到第一个大于等于 start 的位置 i
        i = bisect_right(self.starts, start)
        if i > 0:
            # 检查是否与前一个日程重复
            if self.starts[i-1] == start:
                return False
            if self.ends[self.starts[i-1]] > start:
                return False
            # 检查是否与后一个日程重复
            if i < len(self.starts) and self.starts[i] < end:
                return False
        else:
            # 检查是否与第一个日程重复
            if self.starts and end > self.starts[0]:
                return False
        # 插入新的日程
        self.starts.insert(i, start)
        self.ends[start] = end
        return True


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

Explore

在添加新日程时，必须确保新日程不与已有日程产生时间上的重叠。使用二分查找后，位置i指向的是starts数组中第一个大于等于新日程开始时间的元素位置。检查`i < len(starts)且self.starts[i] < end`是为了确认新日程的结束时间是否与位置i的日程开始时间重叠。如果新日程的结束时间大于等于位置i的日程开始时间，这意味着新日程与位置i的日程有重叠，因此不能添加这个新日程。

使用starts数组和ends字典而不是[start, end]对的列表可以提高搜索和插入操作的效率。starts数组使得可以通过二分查找快速定位新日程的插入位置或检查潜在重叠，而ends字典则允许通过键值对直接访问对应日程的结束时间。如果使用[start, end]列表，则每次查找或插入时都需要线性地检查列表中的每个元素，这在大量日程的情况下会显著增加时间复杂度。使用starts数组和ends字典，理论上可以优化到对数时间复杂度的查找和更高效的插入操作。

使用bisect_right函数确定插入位置意味着在starts数组中查找第一个大于新日程开始时间的元素位置。这种方法确保如果存在与新日程开始时间相同的日程，新日程将被插入在这个已存在日程的后面。这有助于维持starts数组的有序状态，并且允许在检查新日程与前后日程的潜在重叠时，正确地定位和比较时间。因此，这种选择不会错过正确的插入位置，而是有助于保持数据的一致性和正确性。