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

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

news 来源：原创 2025/5/9 11:24:59

文章目录

题目
思路
代码
复杂度分析
- 时间复杂度
- 空间复杂度
结果
总结

题目

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

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

事件能够用一对整数 $s t a r tT im e$ 和 $e n d T im e$ 表示，在一个半开区间的时间 $[s t a r tT im e, e n d T im e)$ 上预定。实数 $x$ 的范围为 $\leq x < endTime$ 。

实现 $M y C a l e n d a r Tw o$ 类：

$M y C a l e n d a r Tw o ()$ 初始化日历对象。
$boolean\ book(int\ startTime,\ int\ endTime)$ 如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 $t r u e$ 。否则，返回 $f a l se$ 并且不要将该日程安排添加到日历中。

示例 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) 将被第二个日程重复预定。

提示：

$\leq start < end \leq 109$
最多调用 $b oo k$ $1000$ 次。

思路

为了实现 $M y C a l e n d a r Tw o$ 类，我们需要跟踪所有的预订和重叠的时间段，以确保不会出现三重预订。我们可以使用两个列表：一个用于存储所有的预订时间段，另一个用于存储所有的双重预订时间段。

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

代码

class MyCalendarTwo {
public:MyCalendarTwo() {// 构造函数，初始化日历对象}bool book(int start, int end) {// 检查新预订是否会导致三重预订for (const auto& [l, r] : overlaps) {if (l < end && start < r) {// 存在三重预订，返回 falsereturn false;}}// 更新双重预订的时间段for (const auto& [l, r] : booked) {if (l < end && start < r) {// 计算重叠区间，并添加到 overlapsoverlaps.emplace_back(max(l, start), min(r, end));}}// 添加新预订到 bookedbooked.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);*/

复杂度分析

时间复杂度

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

空间复杂度

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

结果

在这里插入图片描述

总结

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

文章目录

题目

思路

代码

复杂度分析

时间复杂度

空间复杂度

结果

总结

相关文章：