0732. My Calendar III¶
题目信息¶
- 题号:
0732
- 难度:
Hard
- 主题:
设计、半开区间、最大重叠数
- 原题:
- 重点:
每次预约都会加入日历;调用后返回截至当前所有日程中任一时刻的最大同时覆盖数量,端点相接不重叠
题目重述¶
实现 MyCalendarThree 类。新建对象时日历为空,每次调用 book(startTime, endTime) 都把半开区间 [startTime, endTime) 加入日历。
若存在某个时刻同时落在 k 个已加入日程中,就称这些日程形成一次 k 重预约。每次加入新日程后,返回当前日历能够达到的最大 k。所有预约都会保留,不存在拒绝操作;两个区间只在端点相接时不产生共同覆盖。
每次调用满足 0 <= startTime < endTime <= 10^9,book 最多调用 400 次。同一个对象必须在多次调用之间保留此前加入的全部日程。
自建示例¶
最大重叠数随预约增加:
输入:
操作 = ["MyCalendarThree", "book", "book", "book", "book", "book"]
参数 = [[], [2,6], [4,8], [5,7], [8,10], [1,3]]
输出:[null, 1, 2, 3, 3, 3]
解释:前三次预约后,[5,6) 同时被三个日程覆盖,因此最大重叠数依次升至 3。[8,10) 只与前一区间在端点 8 相接,[1,3) 也不会产生超过 3 的重叠,所以后续返回值保持 3。
完全相同的日程重复加入:
输入:
操作 = ["MyCalendarThree", "book", "book", "book"]
参数 = [[], [12,15], [12,15], [12,15]]
输出:[null, 1, 2, 3]
解释:同一半开区间被加入三次后,其中每个时刻都由三个日程共同覆盖。