【Leetcode】731. 我的日程安排表 II

题目

题目链接🔗
实现一个程序来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。

当三个日程安排有一些时间上的交叉时（例如三个日程安排都在同一时间内），就会产生 三重预订。

事件能够用一对整数 $startTime$ 和 $endTime$ 表示，在一个半开区间的时间 $[startTime,endTime)$ 上预定。实数 $x$ 的范围为 $startTime\le x<endTime$。

实现 $MyCalendarTwo$ 类：

$MyCalendarTwo()$ 初始化日历对象。
$booleanbook(intstartTime,intendTime)$ 如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 $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) 将被第二个日程重复预定。

提示：

1. $0\le start<end\le 109$
2. 最多调用 $book$ $1000$ 次。

思路

为了实现 $MyCalendarTwo$ 类，我们需要跟踪所有的预订和重叠的时间段，以确保不会出现三重预订。我们可以使用两个列表：一个用于存储所有的预订时间段，另一个用于存储所有的双重预订时间段。

在每次新的预订时，检查它是否与任何双重预订时间段重叠。如果有重叠，则这次预订会导致三重预订，因此返回 false。如果没有重叠，检查新的预订与已有的预订时间段的重叠情况，将这些重叠部分添加到双重预订列表中。最后将新的预订添加到预订列表中，并返回 true。

代码

class MyCalendarTwo {
public:
    MyCalendarTwo() {
        // 构造函数，初始化日历对象
    }

    bool book(int start, int end) {
        // 检查新预订是否会导致三重预订
        for (const auto& [l, r] : overlaps) {
            if (l < end && start < r) {
                // 存在三重预订，返回 false
                return false;
            }
        }
        // 更新双重预订的时间段
        for (const auto& [l, r] : booked) {
            if (l < end && start < r) {
                // 计算重叠区间，并添加到 overlaps
                overlaps.emplace_back(max(l, start), min(r, end));
            }
        }
        // 添加新预订到 booked
        booked.emplace_back(start, end);
        return true;
    }

private:
    // 存储所有预订的时间段
    vector<pair<int, int>> booked;
    // 存储所有双重预订的时间段
    vector<pair<int, int>> overlaps;
};

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo* obj = new MyCalendarTwo();
 * bool param_1 = obj->book(startTime,endTime);
 */

复杂度分析

时间复杂度

每次调用 $book$ 方法时，需要遍历所有的双重预订和单次预订列表，检查与新预订的重叠情况。假设已有的预订数量为 $n$，则时间复杂度为 $O(n)$

空间复杂度

使用两个列表来存储预订和双重预订的时间段，因此空间复杂度为 $O(n)$，其中 n 是预订的数量。

结果

总结

使用两个列表分别存储所有的预订时间段和双重预订时间段，可以有效地管理日程安排，确保不会出现三重预订的情况。每次添加新的预订时，先检查是否会导致三重预订，如果不会，则更新双重预订列表和预订列表。