[LeetCode] 每日一题 732. 我的日程安排表 III

题目链接

https://leetcode.cn/problems/my-calendar-iii/description/

题目描述

当 k 个日程存在一些非空交集时（即, k 个日程包含了一些相同时间），就会产生 k 次预订。

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

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

• MyCalendarThree() 初始化对象。

• int book(int startTime, int endTime) 返回一个整数 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 <= startTime < endTime <= 10^9

• 每个测试用例，调用 book 函数最多不超过 400次

题解

解题思路

本题可以看作是一个高级版本的「差分数组」问题。我们需要通过记录时间区间的变化，来实时更新最大重叠预订次数。解决该问题的关键是：

1. 差分思想：对于每个新的预订区间 [start, end)，在 start 时间点增加一个预订量，在 end 时间点减少一个预订量。

2. 有序记录：因为时间点是连续的，我们需要一种方式快速访问并遍历所有关键时间点。为此，可以使用 TreeMap 来存储时间点和它们对应的差分值。

TreeMap 能够通过键值对记录每个时间点的变化，且保证键的有序性，便于我们遍历所有时间点并计算当前的重叠预订次数。

具体步骤：

1. 使用 TreeMap<Integer, Integer> 存储每个时间点的预订变化：

   • key 表示时间点。

   • value 表示该时间点的差分值（开始时 +1，结束时 -1）。

2. 当调用 book 方法时：

   • 更新 TreeMap 中的 start 和 end 的差分值。

   • 遍历 TreeMap 的键值对，累加当前重叠预订次数，记录最大值。

3. 返回最大重叠预订次数。

代码实现

class MyCalendarThree {
    private TreeMap<Integer, Integer> count = new TreeMap<>();

    public MyCalendarThree() {
    }

    public int book(int startTime, int endTime) {
        int ans = 0, max = 0;
        count.put(startTime, count.getOrDefault(startTime, 0) + 1);
        count.put(endTime, count.getOrDefault(endTime, 0) - 1);
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            int freq = entry.getValue();
            max += freq;
            ans = Math.max(max, ans);
        }
        return ans;
    }
}

复杂度分析

1. 时间复杂度：

   • 每次 book 操作会对 start 和 end 进行两次 put 操作，时间复杂度为 O(log N)

   • 每次 book 操作还需遍历 TreeMap 中的所有键值对，最坏情况下 TreeMap 包含 N 个键值对，时间复杂度为 O(N)

   • 单次 book 操作的时间复杂度为 O(N + log N) ≈ O(N)

   • 若有 N 次 book 调用，总时间复杂度为 O(N^2)

2. 空间复杂度：

   • TreeMap 的大小取决于插入的唯一时间点数量，最坏情况下为 O(N)

总结

• 本题采用差分数组思想，结合 TreeMap 的有序性解决动态区间问题

• 优点：实现简单，逻辑清晰

• 缺点：在大量离散时间点的情况下，时间复杂度较高

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