731. 我的日程安排表 II
731. 我的日程安排表 II
🟠 🔖 设计
线段树
数组
二分查找
有序集合
前缀和
🔗 力扣
LeetCode
题目
You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a triple booking.
A triple booking happens when three events have some non-empty intersection (i.e., some moment is common to all the three events.).
The event can be represented as a pair of integers start
and end
that represents a booking on the half-open interval [start, end)
, the range of real numbers x
such that start <= x < end
.
Implement the MyCalendarTwo
class:
MyCalendarTwo()
Initializes the calendar object.boolean book(int start, int end)
Returnstrue
if the event can be added to the calendar successfully without causing a triple booking. Otherwise, returnfalse
and do not add the event to the calendar.
Example 1:
Input
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]
Explanation
MyCalendarTwo myCalendarTwo = new MyCalendarTwo();
myCalendarTwo.book(10, 20); // return True, The event can be booked.
myCalendarTwo.book(50, 60); // return True, The event can be booked.
myCalendarTwo.book(10, 40); // return True, The event can be double booked.
myCalendarTwo.book(5, 15); // return False, The event cannot be booked, because it would result in a triple booking.
myCalendarTwo.book(5, 10); // return True, The event can be booked, as it does not use time 10 which is already double booked.
myCalendarTwo.book(25, 55); // return True, The event can be booked, as the time in [25, 40) will be double booked with the third event, the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.
Constraints:
0 <= start < end <= 10^9
- At most
1000
calls will be made tobook
.
题目大意
实现一个 MyCalendar
类来存放你的日程安排。如果要添加的时间内不会导致三重预订时,则可以存储这个新的日程安排。
MyCalendar
有一个 book(int start, int end)
方法。它意味着在 start
到 end
时间内增加一个日程安排,注意,这里的时间是半开区间,即 [start, end)
, 实数 x
的范围为, start <= x < end
。
当三个日程安排有一些时间上的交叉时(例如三个日程安排都在同一时间内),就会产生三重预订。
每次调用 MyCalendar.book
方法时,如果可以将日程安排成功添加到日历中而不会导致三重预订,返回 true
。否则,返回 false
并且不要将该日程安排添加到日历中。
请按照以下步骤调用 MyCalendar
类:
MyCalendar cal = new MyCalendar();
MyCalendar.book(start, end)
解题思路
- 初始化一个空的
deltas
对象,用于记录时间点的变化。 book
方法:- 对于新事件
[start, end)
,更新deltas
对象,将deltas[start]
加一,deltas[start]
减一。 - 按照时间点顺序遍历deltas
,计算当前重叠事件的数量。 - 遍历所有事件,累加计算重叠数量,如果发现重叠数量达到
3
,表示会导致三重预订,此时撤销之前对deltas
的修改并返回false
。 - 如果没有冲突,表示成功添加事件,返回
true
。
- 对于新事件
复杂度分析
- 时间复杂度:
O(n log n)
,主要是因为我们需要对deltas
的键进行排序。 - 空间复杂度:
O(n)
,用于存储deltas
对象。
代码
var MyCalendarTwo = function () {
this.deltas = {};
};
/**
* @param {number} start
* @param {number} end
* @return {boolean}
*/
MyCalendarTwo.prototype.book = function (start, end) {
// 更新重叠事件计数
this.deltas[start] = (this.deltas[start] || 0) + 1; // 新事件开始
this.deltas[end] = (this.deltas[end] || 0) - 1; // 新事件结束
// 检查重叠数量
let overlap = 0;
for (const time of Object.keys(this.deltas).sort((a, b) => a - b)) {
overlap += this.deltas[time];
if (overlap >= 3) {
// 如果重叠事件达到3,撤销之前的修改
this.deltas[start] -= 1;
this.deltas[end] += 1;
if (this.deltas[start] === 0) delete this.deltas[start];
if (this.deltas[end] === 0) delete this.deltas[end];
return false; // 返回 false,表示添加失败
}
}
return true; // 成功添加事件,返回 true
};
/**
* Your MyCalendarTwo object will be instantiated and called as such:
* var obj = new MyCalendarTwo()
* var param_1 = obj.book(start,end)
*/
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
729 | 我的日程安排表 I | [✓] | 设计 线段树 数组 2+ | |
732 | 我的日程安排表 III | 设计 线段树 二分查找 2+ |