[LeetCode] 每日一题 731. 我的日程安排表 II

题目链接

题目描述

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

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

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

实现 MyCalendarTwo 类：

• MyCalendarTwo() 初始化日历对象。

• boolean book(int startTime, int endTime) 如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。

示例输入

示例

输入：
["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) 将被第二个日程重复预定。

提示

• 0 <= start < end <= 10^9

• 每个测试用例，调用 book 方法的次数最多不超过 1000 次

题解

解题思路

本题要求实现一个程序，用于存储日程安排，并确保不会出现三重预订。关键点在于：

1. 每个事件由一对整数 [startTime, endTime) 表示，表示半开区间的时间段

2. 如果三个事件在某一时间点重叠，则不能将新事件添加到日程安排中

解法的核心思想是差分：

• 我们用一个有序映射 timeMap 记录每个时间点的变化量：

  • 在 startTime 加 1，表示从这个时间点开始新增一个活动

  • 在 endTime 减 1，表示从这个时间点开始减少一个活动

• 然后，通过累加差分数组的值，我们可以得到每个时间点的预订数。如果某时间点的预订数超过 2，则意味着出现三重预订

关键步骤：

1. 在尝试插入一个事件前，先将其差分变化加入 timeMap

2. 遍历累加计算预订数，若发现预订数超过 2，说明插入失败，并需要撤回操作

3. 否则，插入成功

这种方法充分利用了差分的思想和有序映射，避免了直接检查所有可能的时间点的复杂操作

代码实现

class MyCalendarTwo {
    private final Map<Integer, Integer> timeMap = new TreeMap<>();

    public MyCalendarTwo() {
    }

    public boolean book(int startTime, int endTime) {
        // 更新差分
        timeMap.merge(startTime, 1, Integer::sum);
        timeMap.merge(endTime, -1, Integer::sum);

        int activeBookings = 0;
        for (int delta : timeMap.values()) {
            activeBookings += delta;
            if (activeBookings > 2) {
                // 三重预订，回退操作
                timeMap.merge(startTime, -1, Integer::sum);
                timeMap.merge(endTime, 1, Integer::sum);
                return false;
            }
        }
        return true;
    }
}

复杂度分析

1. 时间复杂度：

   • 每次 book 操作需要将新事件的差分加入 timeMap，这是 O(log n)

   • 然后，需要遍历 timeMap 的所有键值对，计算当前的最大预订数。这是 O(n)

   • 因此，每次 book 的时间复杂度为 O(n)

   • 对于总共 n 次插入操作，总时间复杂度为 O(n^2)

2. 空间复杂度：

   • 每个事件的 startTime 和 endTime 都可能是唯一的，因此 timeMap 最多存储 2n 个键值对

   • 空间复杂度为 O(n)

总结

本题利用差分思想和 TreeMap 的有序特性，解决了日程安排问题

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。