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

执行结果：通过

题目 732 我的日程安排表 III

当 k 个日程存在一些非空交集时（即, k 个日程包含了一些相同时间），就会产生 k 次预订。

给你一些日程安排 [startTime, endTime) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。

实现一个 MyCalendarThree 类来存放你的日程安排，你可以一直添加新的日程安排。

• MyCalendarThree() 初始化对象。
• int book(int startTime, int endTime) 返回一个整数 k ，表示日历中存在的 k 次预订的最大值。

示例：

输入：
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
输出：
[null, 1, 1, 2, 3, 3, 3]解释：
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // 返回 1 ，第一个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(50, 60); // 返回 1 ，第二个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(10, 40); // 返回 2 ，第三个日程安排 [10, 40) 与第一个日程安排相交，所以最大 k 次预订是 2 次预订。
myCalendarThree.book(5, 15); // 返回 3 ，剩下的日程安排的最大 k 次预订是 3 次预订。
myCalendarThree.book(5, 10); // 返回 3
myCalendarThree.book(25, 55); // 返回 3

提示：

• 0 <= startTime < endTime <= 109
• 每个测试用例，调用 book 函数最多不超过 400次

代码以及解题思路

代码

class MyCalendarThree:def __init__(self):from collections import defaultdictself.timeline = defaultdict(int)def book(self, startTime: int, endTime: int) -> int:self.timeline[startTime] += 1self.timeline[endTime] -= 1active = 0maxK = 0for time in sorted(self.timeline):active += self.timeline[time]maxK = max(maxK, active)return maxK

解题思路：

1. 数据结构选择：
   • 使用 defaultdict(int) 来存储时间线，其中键是时间（整数），值是该时间点上预定数量的变化量（增加或减少）。
2. 预定处理：
   • 当一个新的时间段 [startTime, endTime) 被预定时，在 startTime 时刻将预定数量增加 1，在 endTime 时刻将预定数量减少 1。这样做是为了在遍历时间线时，通过累加这些变化量来跟踪任意给定时间点的活动预定数量。
3. 计算最大同时预定数量：
   • 遍历排序后的时间线，累加每个时间点的变化量（即 active += self.timeline[time]），以跟踪当前活动的预定数量。
   • 在遍历过程中，记录并更新遇到的最大活动预定数量（即 maxK = max(maxK, active)）。
4. 返回结果：
   • 返回记录的最大同时预定数量。