我的日程安排表 I

难度:

标签:

题目描述

代码结果

运行时间: 121 ms, 内存: 16.9 MB

/*
 * MyCalendar class implementation using Java Stream API.
 * Similar to the previous solution but leverages Java Streams for cleaner and more readable code.
 * The book method uses a stream to check for overlapping intervals.
 * If no overlaps are found, the new booking is added to the list and the method returns true; otherwise, it returns false.
 */
import java.util.ArrayList;
import java.util.List;

class MyCalendar {
    private List<int[]> calendar;

    public MyCalendar() {
        calendar = new ArrayList<>();
    }

    public boolean book(int start, int end) {
        boolean overlap = calendar.stream().anyMatch(event -> Math.max(event[0], start) < Math.min(event[1], end));
        if (overlap) {
            return false;
        }
        calendar.add(new int[]{start, end});
        return true;
    }
}

解释

方法:

该题解使用两个数组 starts 和 ends 来分别存储每个日程的开始时间和结束时间。当需要添加新的日程时，使用二分查找来找到 starts 数组中第一个大于等于新日程开始时间的位置 i。然后进行以下检查： 1. 如果 i>0 且 starts[i-1] 等于新日程的开始时间，说明存在重复预订，返回 False。 2. 如果 i>0 且前一个日程的结束时间大于新日程的开始时间，说明存在重复预订，返回 False。 3. 如果 i

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

在使用二分查找找到插入位置后，为什么需要检查i < len(starts)且self.starts[i] < end来判断与后一个日程是否重叠？

▷

在添加新日程时，必须确保新日程不与已有日程产生时间上的重叠。使用二分查找后，位置i指向的是starts数组中第一个大于等于新日程开始时间的元素位置。检查`i < len(starts)且self.starts[i] < end`是为了确认新日程的结束时间是否与位置i的日程开始时间重叠。如果新日程的结束时间大于等于位置i的日程开始时间，这意味着新日程与位置i的日程有重叠，因此不能添加这个新日程。

🦆

插入新日程时，为什么选择使用starts数组和ends字典的结构，而不是存储日程为一对[start, end]的列表？这种数据结构选择对性能有何影响？

▷

使用starts数组和ends字典而不是[start, end]对的列表可以提高搜索和插入操作的效率。starts数组使得可以通过二分查找快速定位新日程的插入位置或检查潜在重叠，而ends字典则允许通过键值对直接访问对应日程的结束时间。如果使用[start, end]列表，则每次查找或插入时都需要线性地检查列表中的每个元素，这在大量日程的情况下会显著增加时间复杂度。使用starts数组和ends字典，理论上可以优化到对数时间复杂度的查找和更高效的插入操作。

🦆

二分查找使用的是bisect_right函数，这个选择对于日程的插入和检查逻辑有何影响，是否可能会错过正确的插入位置？

▷

使用bisect_right函数确定插入位置意味着在starts数组中查找第一个大于新日程开始时间的元素位置。这种方法确保如果存在与新日程开始时间相同的日程，新日程将被插入在这个已存在日程的后面。这有助于维持starts数组的有序状态，并且允许在检查新日程与前后日程的潜在重叠时，正确地定位和比较时间。因此，这种选择不会错过正确的插入位置，而是有助于保持数据的一致性和正确性。

相关问题

我的日程安排表 II

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

MyCalendar 有一个 book(int start, int end)方法。它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end。

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

每次调用 MyCalendar.book方法时，如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。

请按照以下步骤调用MyCalendar 类: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

示例：

MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(50, 60); // returns true
MyCalendar.book(10, 40); // returns true
MyCalendar.book(5, 15); // returns false
MyCalendar.book(5, 10); // returns true
MyCalendar.book(25, 55); // returns true
解释： 
前两个日程安排可以添加至日历中。 第三个日程安排会导致双重预订，但可以添加至日历中。
第四个日程安排活动（5,15）不能添加至日历中，因为它会导致三重预订。
第五个日程安排（5,10）可以添加至日历中，因为它未使用已经双重预订的时间10。
第六个日程安排（25,55）可以添加至日历中，因为时间 [25,40] 将和第三个日程安排双重预订；
时间 [40,50] 将单独预订，时间 [50,55）将和第二个日程安排双重预订。

提示：

每个测试用例，调用 MyCalendar.book 函数最多不超过 1000次。
调用函数 MyCalendar.book(start, end)时， start 和 end 的取值范围为 [0, 10^9]。

我的日程安排表 III

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

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

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

MyCalendarThree() 初始化对象。
int book(int start, int end) 返回一个整数 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 <= start < end <= 10⁹
每个测试用例，调用 book 函数最多不超过 400次

自除数统计不同回文子序列