日期: 2025 年 1 月 4 日

732.我的日程安排表III

目标

当 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次

思路

参考 731.我的日程安排表II，同样的思路，只不过求得是相交区间数量的最大值。

代码

/**
 * @date 2025-01-04 15:40
 */
public class MyCalendarThree {

    TreeMap<Integer, Integer> cnt = new TreeMap<>();

    public MyCalendarThree() {

    }

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

性能