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 次

Reference

题解¶

基本思路： 和 731. 我的日程安排表 II 类似，使用嵌套列表存储所有时间段，第\(i\)个列表存储被访问\(i\)次的时间段。每一轮插入一个新的区间后，(1) 更新本层记录的区间，(2) 将重复的区间插入到下一层中。最终，嵌套层数即为最大的预订次数。

代码如下：

from typing import List
import bisect

class MyCalendarThree:

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

    def insert(self, startTime: int, endTime: int, level: int):
        if level == len(self.times):
            self.times.append([])
        left_idx = bisect.bisect_right(self.times[level], startTime)
        right_idx = bisect.bisect_left(self.times[level], endTime)

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

        new = [startTime, endTime]
        if left_idx % 2:
            new.pop(0)
        elif left and left[-1] == new[0]:
            left.pop(-1), new.pop(0)
        if right_idx % 2:
            new.pop(-1)
        elif right and right[0] == new[-1]:
            right.pop(0), new.pop(-1)
        self.times[level] = [*left, *new, *right]

        for i in range((left_idx + 1) % 2, len(mid), 2):
            if i + 1 >= len(mid):
                break
            self.insert(mid[i], mid[i + 1], level + 1)

    def book(self, startTime: int, endTime: int) -> int:
        self.insert(startTime, endTime, 0)
        return len(self.times)


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

732. 我的日程安排表 III¶

题目¶

题解¶

评论