【Leetcode 每日一题】732. 我的日程安排表 III

问题背景

当 $k$ 个日程存在一些非空交集时（即，$k$ 个日程包含了一些相同时间），就会产生 $k$ 次预订。
给你一些日程安排 $[startTime,endTime)$，请你在每个日程安排添加后，返回一个整数 $k$，表示所有先前日程安排会产生的最大 $k$ 次预订。
实现一个 MyCalendarThree 类来存放你的日程安排，你可以一直添加新的日程安排。

• MyCalendarThree() 初始化对象。
• int book(int startTime, int endTime) 返回一个整数 $k$，表示日历中存在的 $k$ 次预订的最大值。

数据约束

• $0\le startTime<endTime\le 10^9$
• 每个测试用例，调用 book 函数最多不超过 $400$ 次

解题过程

一维差搭配前缀和，能够快速地得到一个范围内每个数组都进行加减操作的结果。
由于这题数据量比较大，需要用有序映射作为哈希表来模拟数组。这样在遍历集合的过程中，可以方便地得到每个时间点出现的次数。
需要注意的是，一般情况下一维差分是在右端点的后一个位置进行取消操作，但是本题中所给的区间左闭右开，不需要修正。

具体实现

class MyCalendarThree {
    // TreeMap 会根据键的大小维护元素的顺序
    private static final TreeMap<Integer, Integer> map = new TreeMap<>();

    public MyCalendarThree() {
        map.clear();
    }
    
    public int book(int startTime, int endTime) {
        // 构造差分数组
        map.merge(startTime, 1, Integer::sum);
        map.merge(endTime, -1, Integer::sum);
        // times 可以看作前缀和，遍历到某个位置上，就是它出现的总次数
        int res = 0, times = 0;
        for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
            times += entry.getValue();
            res = Math.max(res, times);
        }
        return res;
    }
}

/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * MyCalendarThree obj = new MyCalendarThree();
 * int param_1 = obj.book(startTime,endTime);
 */