731. 我的日程安排表 II¶

难度：中等

题目¶

实现一个程序来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。

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

事件能够用一对整数 startTime 和 endTime 表示，在一个半开区间的时间 [startTime, endTime) 上预定。实数 x 的范围为 startTime <= x < endTime。

实现 MyCalendarTwo 类：

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

示例 1：

输入：

["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]

输出：

[null, true, true, true, false, true, true]

解释：

MyCalendarTwo myCalendarTwo = new MyCalendarTwo();
myCalendarTwo.book(10, 20); // 返回 True，能够预定该日程。
myCalendarTwo.book(50, 60); // 返回 True，能够预定该日程。
myCalendarTwo.book(10, 40); // 返回 True，该日程能够被重复预定。
myCalendarTwo.book(5, 15);  // 返回 False，该日程导致了三重预定，所以不能预定。
myCalendarTwo.book(5, 10); // 返回 True，能够预定该日程，因为它不使用已经双重预订的时间 10。
myCalendarTwo.book(25, 55); // 返回 True，能够预定该日程，因为时间段 [25, 40) 将被第三个日程重复预定，时间段 [40, 50) 将被单独预定，而时间段 [50, 55) 将被第二个日程重复预定。

提示：

0 <= start < end <= 109
最多调用 book 1000 次。

Reference

题解¶

基本思路： 使用两个列表存放区间开始的时间和结束的时间。这些列表满足：(1) 列表单调非减；(2) 偶数下标的时间是开始时间，奇数下标的时间是结束时间。第一个列表存储的是至少预定过一次的时间段，第二个列表存储的是预定两次的时间段。

如果新的时间段和第二个列表中的时间段有重叠，说明有三重预订。可以用729. 我的日程安排表 I的方法在第二个列表中检查是否有重叠的时间段。否则，按照如下的方式将新的时间段加入到列表中：

更新第一个列表，合并已有的区间和新的区间，
检查是否有重叠的时间段
将重叠的时间段加入第二个列表。

代码如下：

from typing import List
import bisect

class MyCalendarTwo:

    def __init__(self):
        self.times: List[int] = []
        self.double_times: List[int] = []

    def _check(self, startTime: int, endTime: int) -> bool:
        # Only check in the time span visited twice
        x = bisect.bisect_right(self.double_times, startTime)
        y = bisect.bisect_left(self.double_times, endTime)

        if x != y:
            return False
        if x % 2:
            return False
        return True

    def insert_double(self, start: int, end: int) -> None:
        bisect.insort_left(self.double_times, end)
        bisect.insort_right(self.double_times, start)

    def update(self, startTime: int, endTime: int) -> None:
        left_idx = bisect.bisect_right(self.times, startTime)
        right_idx = bisect.bisect_left(self.times, endTime)

        left = self.times[:left_idx]
        mid = [startTime, *self.times[left_idx:right_idx], endTime]
        right = self.times[right_idx:]

        # We only care about mid
        new = [startTime, endTime]
        if left_idx % 2: # Left side falls in the time span
            new.pop(0)
        elif left and left[-1] == new[0]: # Merge time span
            left.pop(-1), new.pop(0)
        if right_idx % 2: # Right side falls in the time span
            new.pop(-1)
        elif right and right[0] == new[-1]: # Merge time span
            right.pop(0), new.pop(-1)

        # Re-merge all the time span
        self.times = [*left, *new, *right]

        # Update time span visited twice
        for i in range((left_idx + 1) % 2, len(mid), 2):
            if i + 1 >= len(mid):
                break
            self.insert_double(mid[i], mid[i + 1])

    def book(self, startTime: int, endTime: int) -> bool:
        if not self._check(startTime, endTime):
            return False
        self.update(startTime, endTime)
        return True


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

731. 我的日程安排表 II¶

题目¶

题解¶

评论