729. 我的日程安排表 I

🟠   🔖  设计 线段树 数组 二分查找 有序集合  🔗 力扣 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 double booking.

A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both 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 MyCalendar class:

• MyCalendar() 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 double booking. Otherwise, return false and do not add the event to the calendar.

Example 1:

Input

["MyCalendar", "book", "book", "book"]

[[], [10, 20], [15, 25], [20, 30]]

Output

[null, true, false, true]

Explanation

MyCalendar myCalendar = new MyCalendar();

myCalendar.book(10, 20); // return True

myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.

myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.

Constraints:

• 0 <= start < end <= 10^9
• At most 1000 calls will be made to book.

题目大意

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会造成 重复预订 ，则可以存储这个新的日程安排。

当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生 重复预订 。

日程可以用一对整数 start 和 end 表示，这里的时间是半开区间，即 [start, end), 实数 x 的范围为， start <= x < end 。

实现 MyCalendar 类：

• MyCalendar() 初始化日历对象。
• boolean book(int start, int end) 如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 true 。否则，返回 false 并且不要将该日程安排添加到日历中。

解题思路

思路一：遍历

• 遍历已添加的日历，逐一判断新的日程安排 [start, end) 和已有的日程安排 [s, e) 是否重复
• 当 start < e && end > s 时，代表两个区间重复了；
• 一旦发现重复，则返回 false；
• 全部遍历完都没有重复，则将新日程加入到日程数组中，并返回 true；

复杂度分析

• 时间复杂度：O(n)，其中 n 是已预定的时间段数量。每次调用 book 方法时，都需要遍历整个 calendar 数组以检查是否有重叠时间段。
• 空间复杂度：O(n)``，数组 calendar存储n` 个预定的时间段。

---

思路二：二分查找

如果每次添加新的日程 [start, end) 时，按照 start 的大小顺序插入，查找的时候就可以用二分查找，将时间复杂度降低到 O(log n)。

更新二分查找范围的时候要注意，对于已有的日程安排 [s, e)，要根据 e 和 start的关系来判断查找范围：

• 若 e < start，则两个日程无交集，可以直接缩小范围；
  • 如果新时间段的 start 大于等于当前比较时间段的 end，更新 left 指针；
  • 如果新时间段的 end 小于当前比较时间段的 start，更新 right 指针；
• 若 e > start，则两个日程有重合的可能，返回 false；

复杂度分析

• 时间复杂度：O(log n)，其中 n 是已预定的时间段数量。由于时间段按顺序插入，因此可以对 calendar 进行二分查找，查找并插入新时间段的时间复杂度为 O(log n)。
• 空间复杂度：O(n)``，数组 calendar存储n` 个预定的时间段。

代码

遍历

var MyCalendar = function () {
	this.calendar = [];
};

/**
 * @param {number} start
 * @param {number} end
 * @return {boolean}
 */
MyCalendar.prototype.book = function (start, end) {
	for (let [s, e] of this.calendar) {
		if (start < e && end > s) return false;
	}
	this.calendar.push([start, end]);
	return true;
};

/**
 * Your MyCalendar object will be instantiated and called as such:
 * var obj = new MyCalendar()
 * var param_1 = obj.book(start,end)
 */

二分查找

var MyCalendar = function () {
	this.calendar = [];
};

/**
 * @param {number} start
 * @param {number} end
 * @return {boolean}
 */
MyCalendar.prototype.book = function (start, end) {
	let left = 0,
		right = this.calendar.length - 1;

	// 二分查找
	while (left <= right) {
		let mid = ((left + right) / 2) | 0;
		const [s, e] = this.calendar[mid];

		// 时间重合，直接返回 false
		if (start < e && end > s) return false;

		// 更新二分查找范围
		if (start >= e) {
			left = mid + 1;
		} else {
			right = mid - 1;
		}
	}
	this.calendar.splice(left, 0, [start, end]);
	return true;
};

/**
 * Your MyCalendar object will be instantiated and called as such:
 * var obj = new MyCalendar()
 * var param_1 = obj.book(start,end)
 */

相关题目

题号	标题	题解	标签	难度
731	我的日程安排表 II	[✓]	设计 线段树 数组 3+
732	我的日程安排表 III		设计 线段树 二分查找 2+
2446	判断两个事件是否存在冲突		数组 字符串