LeetCode 题解工作台
我的日程安排表 II
实现一个程序来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。 当三个日程安排有一些时间上的交叉时（例如三个日程安排都在同一时间内），就会产生 三重预订 。 事件能够用一对整数 startTime 和 endTime 表示，在一个半开区间的时间 [startTim…
6
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·搜索·答案·空间
答案摘要
我们可以利用差分的思想，将每个时间点的预定情况记录下来，然后遍历所有时间点，统计当前时间点的预定情况，如果预定次数超过 次，则返回 。否则，返回 。 时间复杂度 ，空间复杂度 ，其中 表示日程安排的数量。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
实现一个程序来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。
当三个日程安排有一些时间上的交叉时（例如三个日程安排都在同一时间内），就会产生 三重预订。
事件能够用一对整数 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- 最多调用
book1000 次。
解题思路
方法一：差分
我们可以利用差分的思想，将每个时间点的预定情况记录下来，然后遍历所有时间点，统计当前时间点的预定情况，如果预定次数超过 次，则返回 。否则，返回 。
时间复杂度 ，空间复杂度 ，其中 表示日程安排的数量。
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
# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(startTime,endTime)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N) per booking in the worst case due to overlap checks, and space complexity is O(N) to store single- and double-booked intervals. |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
Look for efficient interval insertion and overlap detection.
- question_mark
Check if the candidate correctly handles double bookings without creating triples.
- question_mark
Listen for binary search usage when scanning for potential conflicts.
常见陷阱
外企场景- error
Failing to check double-booked intervals first, leading to inadvertent triple bookings.
- error
Inserting events without maintaining sorted interval lists, which slows down future checks.
- error
Overlapping calculations off by one, misunderstanding the half-open interval definition.
进阶变体
外企场景- arrow_right_alt
Modify to allow at most K bookings per time slot instead of two.
- arrow_right_alt
Use a segment tree to handle a larger range of time values more efficiently.
- arrow_right_alt
Implement the same calendar logic but for continuous real-number time ranges instead of integer times.