0731.md

title	description	keywords
731. 我的日程安排表 II	LeetCode,731. 我的日程安排表 II,我的日程安排表 II,My Calendar II,解题思路,设计,线段树,数组,二分查找,有序集合,前缀和	LeetCode 731. 我的日程安排表 II 我的日程安排表 II My Calendar II 解题思路 设计 线段树 数组 二分查找 有序集合 前缀和

731. 我的日程安排表 II

🟠 Medium  🔖  设计 线段树 数组 二分查找 有序集合 前缀和  🔗 力扣 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) Returns true if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return false 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 to book.

题目大意

实现一个 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)

解题思路

1. 初始化一个空的 deltas 对象，用于记录时间点的变化。
2. 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+	Medium
732	我的日程安排表 III		设计 线段树 二分查找 2+	Hard