Leetcode打卡：我的日程安排表II

执行结果：通过

题目 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 次。

代码以及解题思路

代码

from sortedcontainers import SortedDict
class MyCalendarTwo:
    def __init__(self):
        self.sd = SortedDict()

    def book(self, startTime: int, endTime: int) -> bool:
        self.sd[startTime] = self.sd.get(startTime, 0) + 1
        self.sd[endTime] = self.sd.get(endTime, 0) - 1
        s = 0
        for v in self.sd.values():
            s += v
            if s > 2:
                self.sd[startTime] -= 1
                self.sd[endTime] += 1
                return False
        return True

解题思路：

. 初始化 SortedDict

• 在 MyCalendarTwo 类的构造函数 __init__ 中，创建了一个 SortedDict 实例 self.sd。SortedDict 是一个自动保持键排序的字典，非常适合于按时间顺序处理键值对。

2. book 方法

• book 方法接受两个参数 startTime 和 endTime，分别表示新的会议的开始时间和结束时间。
• 方法的目的是检查并尝试预订这个新的会议时间段，如果在任何时间点上同时进行的会议数不超过 2 个，则返回 True，否则返回 False。

3. 处理会议的开始和结束

• 对于新的会议时间段，我们在 SortedDict 中记录它的开始和结束。
  • 使用 self.sd[startTime] = self.sd.get(startTime, 0) + 1 增加 startTime 处的计数，表示一个新的会议开始。
  • 使用 self.sd[endTime] = self.sd.get(endTime, 0) - 1 减少 endTime 处的计数，表示一个会议结束。
• 这样，通过遍历 SortedDict 的值，我们可以计算出任意时间点上的会议数量。

4. 遍历并检查会议重叠

• 初始化一个变量 s 为 0，用于跟踪当前时间点的会议数量。
• 遍历 SortedDict 的值（这些值代表会议的开始和结束事件导致的计数变化），逐步更新 s。
  • 每当遇到一个开始事件（正数），将 s 增加相应的值。
  • 每当遇到一个结束事件（负数），将 s 减少相应的值。
• 在遍历过程中，如果 s 的值在任何时间点超过了 2，表示此时有三个或更多的会议同时进行，因此不能添加新的会议时间段。
  • 如果发生这种情况，我们需要回滚对 SortedDict 的修改（即减少 startTime 的计数并增加 endTime 的计数），然后返回 False。

5. 返回结果

• 如果遍历结束后没有超过 2 个会议同时进行的情况，则新的会议时间段可以被成功预订，返回 True。

总结

通过巧妙地使用 SortedDict 来记录会议的开始和结束，并实时跟踪任意时间点上的会议数量，这个算法高效地解决了检查会议时间段是否可以添加的问题。这种方法避免了直接检查所有可能的时间重叠，从而大大提高了效率。