当前位置：首页 > article >正文

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

article 2025/1/6 12:14:17

执行结果：通过

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