我的日程安排表 II

难度:

标签:

题目描述

代码结果

运行时间: 180 ms, 内存: 0.0 MB

/*
 * 思路：利用Java Streams和集合框架来简化区间的处理。主要思想是使用两个列表来跟踪日程安排和双重预订区间。
 * 在每次调用book方法时，我们首先检查新的区间是否会导致三重预订。如果没有，则检查并记录新的双重预订区间，最后将新日程添加到日程安排列表中。
 */
 
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
 
class MyCalendar {
    private List<int[]> calendar;
    private List<int[]> overlaps;
 
    public MyCalendar() {
        calendar = new ArrayList<>();
        overlaps = new ArrayList<>();
    }
 
    public boolean book(int start, int end) {
        // 检查三重预订冲突
        boolean hasTripleBooking = overlaps.stream()
            .anyMatch(overlap -> start < overlap[1] && end > overlap[0]);
        if (hasTripleBooking) return false;
 
        // 记录新的双重预订区间
        List<int[]> newOverlaps = calendar.stream()
            .filter(event -> start < event[1] && end > event[0])
            .map(event -> new int[]{Math.max(start, event[0]), Math.min(end, event[1])})
            .collect(Collectors.toList());
        overlaps.addAll(newOverlaps);
 
        // 添加新的日程安排
        calendar.add(new int[]{start, end});
        return true;
    }
}
 
/*
 * 示例：
 * MyCalendar cal = new MyCalendar();
 * cal.book(10, 20); // returns true
 * cal.book(50, 60); // returns true
 * cal.book(10, 40); // returns true
 * cal.book(5, 15); // returns false
 * cal.book(5, 10); // returns true
 * cal.book(25, 55); // returns true
 */

解释

方法:

这个题解使用了有序列表来维护当前已预订的日程安排的开始和结束时间。当要预订一个新的日程时，首先用二分查找找到新日程的开始时间在结束时间列表中的位置ind1，以及结束时间在开始时间列表中的位置ind2。然后检查ind1到ind2-1范围内的日程，看是否会产生三重预订（即某个已有日程的结束时间大于下一个日程的开始时间）。如果不会导致三重预订，就将新日程的开始和结束时间分别插入到开始时间列表和结束时间列表的合适位置。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

题解中的二分查找用于寻找插入位置，具体是如何通过这两个位置（ind1和ind2）判断是否会产生三重预订的？

▷

在题解中，二分查找用于确定新日程的开始时间和结束时间应插入的位置。通过找到这两个位置，可以确定新日程与现有日程的重叠部分。具体来说，ind1是新日程开始时间应该插入的位置，表示所有结束时间小于或等于新日程开始时间的日程都不会与新日程重叠。同理，ind2是新日程结束时间应该插入的位置，表示所有开始时间大于或等于新日程结束时间的日程也不会与新日程重叠。因此，只需要检查从ind1到ind2-1的日程，这些是可能与新日程重叠的日程。如果在这个范围内的任何已有日程的结束时间大于下一个日程的开始时间，意味着存在至少三个日程在某个时间点重叠，从而导致三重预订。

🦆

在进行三重预订检查时，为什么只检查从 ind1 到 ind2-1 的范围内的日程？这个范围是否能覆盖所有可能产生三重预订的情况？

▷

检查从ind1到ind2-1的范围是因为这些位置表示的日程是新日程可能会直接影响的日程，即这些日程的结束时间在新日程的开始时间之后，且开始时间在新日程的结束时间之前。这样的日程表示它们与新日程有时间上的重叠。在这个范围之外的日程，要么完全在新日程开始之前结束，要么开始于新日程结束之后，因此不会与新日程产生直接的时间重叠。因此，这个范围确实能够覆盖所有可能与新日程产生三重预订的情况。

🦆

题解中提到，在最坏情况下，检查是否产生三重预订的循环需要遍历所有已有日程。在什么情况下会发生这种最坏的情况？

▷

最坏的情况出现在新日程的时间范围非常广泛，以至于它可能与所有已有的日程重叠。例如，如果一个新日程的开始时间非常早，结束时间非常晚，那么新日程的时间范围可能覆盖所有或大部分已有日程。在这种情况下，由于ind1很小（接近0），而ind2很大（接近已有日程数量），检查是否产生三重预订的循环需要遍历从ind1到ind2-1的所有日程，即几乎是所有已有的日程，这就是最坏的情况。

相关问题

我的日程安排表 I

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会造成 重复预订 ，则可以存储这个新的日程安排。

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

日程可以用一对整数 start 和 end 表示，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end 。

实现 MyCalendar 类：

MyCalendar() 初始化日历对象。
boolean book(int start, int end) 如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 true 。否则，返回 false 并且不要将该日程安排添加到日历中。

示例：

输入：
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
输出：
[null, true, false, true]

解释：
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False ，这个日程安排不能添加到日历中，因为时间 15 已经被另一个日程安排预订了。
myCalendar.book(20, 30); // return True ，这个日程安排可以添加到日历中，因为第一个日程安排预订的每个时间都小于 20 ，且不包含时间 20 。

提示：

0 <= start < end <= 10⁹
每个测试用例，调用 book 方法的次数最多不超过 1000 次。

我的日程安排表 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次

统计不同回文子序列我的日程安排表 III