我的日程安排表 III

难度:

标签:

题目描述

代码结果

运行时间: 93 ms, 内存: 16.5 MB

// 思路：类似于Java实现，使用TreeMap记录时间点的事件变化。使用Stream遍历Map的values计算最大事件重叠数。

import java.util.TreeMap;

public class MyCalendarThree {
    private TreeMap<Integer, Integer> timeline;

    public MyCalendarThree() {
        timeline = new TreeMap<>();
    }

    public int book(int start, int end) {
        timeline.put(start, timeline.getOrDefault(start, 0) + 1);
        timeline.put(end, timeline.getOrDefault(end, 0) - 1);

        int[] maxBookings = new int[1];
        timeline.values().stream()
            .mapToInt(value -> value)
            .reduce(0, (ongoing, events) -> {
                ongoing += events;
                maxBookings[0] = Math.max(maxBookings[0], ongoing);
                return ongoing;
            });

        return maxBookings[0];
    }
}

解释

方法:

这个题解使用了差分数组的思路。具体来说，它维护了两个有序数组 s 和 e，分别存储所有日程的开始时间和结束时间。当插入一个新的日程 [start, end) 时，它先通过二分查找找到 start 在 e 中的插入位置 ind1，以及 end 在 s 中的插入位置 ind2。然后从 ind1 开始遍历，用一个变量 curr 记录当前的预订次数，如果遇到一个日程的开始时间小于当前指针 p1 指向的日程的结束时间，说明发生了交叉，curr 就加 1。每次更新 curr 后都要更新答案 cap。最后再将 start 插入 s，将 end 插入 e。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

如何保证数组s和e始终保持有序？插入操作是否会影响两个数组的性能？

▷

数组s和e保持有序是通过使用Python的标准库函数`bisect.insort`实现的，该函数可以在保持列表有序的情况下插入新元素。确实，插入操作会影响性能，因为在有序数组中插入一个元素的时间复杂度通常是O(n)，其中n是数组的长度。这意味着每次插入都需要在找到插入点后，移动插入点后的所有元素以保持数组的有序性。这在频繁插入且数据量较大时会相对耗时。

🦆

在算法中，ind1和ind2的定义及计算方式是否确保了不会错过任何重叠区间？

▷

ind1是使用`bisect_right`计算的，这意味着它会找到第一个大于start的结束时间的位置，在这之前的所有结束时间都不可能与新的开始时间start重叠。ind2是使用`bisect_left`计算的，这意味着它会找到第一个不小于end的开始时间的位置。这种方式确保了所有可能与新日程[start, end)重叠的区间都会在start和end之间被检查到，从而不会错过任何重叠区间。

🦆

函数中的for循环中，p1指针的更新逻辑是否可能导致遗漏检查某些交叉的日程？

▷

p1指针在遍历过程中的更新逻辑是如果当前日程的开始时间小于p1指向的日程的结束时间，则认为发生了交叉，否则p1递增。这种逻辑确保了只要存在交叉，p1就不会递增，因此不会遗漏任何交叉的日程。然而，此逻辑依赖于数组s和e的正确和有序，任何错误或处理不当都可能导致遗漏或错误计算。

🦆

算法中使用了bisect_right和bisect_left，这两个函数的选择对算法的正确性和效率有何影响？

▷

使用`bisect_right`和`bisect_left`确保了在有序数组中正确地找到插入位置。`bisect_right`返回的是插入点右侧的位置，适用于找到所有小于等于给定值的元素的场景；而`bisect_left`返回的是插入点左侧的位置，适用于找到所有小于给定值的元素的场景。这两个函数的选择关键影响了算法的正确性，确保了不会错过检查任何可能的重叠日程。在效率方面，这两个函数的执行时间复杂度为O(log n)，使得查找插入位置比较高效，但实际插入操作仍然是O(n)。

相关问题

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

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

我的日程安排表 II 图像渲染