What is the main strategy to prevent double bookings in My Calendar I?

Use a sorted list of existing intervals and binary search to find the insertion point, then check adjacent intervals for conflicts.

How do half-open intervals affect booking logic?

Half-open intervals [start, end) mean the start time is included but the end is excluded, so two events touching at boundaries do not overlap.

Can we optimize beyond linear scans for this problem?

Yes, binary search over the sorted event list reduces the number of comparisons from O(N) to O(log N) per booking.

What are common mistakes when implementing this calendar?

Ignoring boundary conditions, failing to check both neighbors for overlap, or using inefficient scans for each insertion.

Why is this problem categorized under binary search over valid answer space?

Because each booking requires locating the correct interval position in a sorted list, binary search efficiently determines whether insertion is valid.

#729

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

我的日程安排表 I

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会造成重复预订，则可以存储这个新的日程安排。当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生重复预订。日程可以用一对整数 startTime 和 endTime 表示，这里的时间是半…

数组二分查找设计线段树有序集合

题目描述

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

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

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

实现 MyCalendar 类：

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

示例：

输入：
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
输出：
[null, true, false, true]

解释：
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False ，这个日程安排不能添加到日历中，因为时间 15 已经被另一个日程安排预订了。
myCalendar.book(20, 30); // return True ，这个日程安排可以添加到日历中，因为第一个日程安排预订的每个时间都小于 20 ，且不包含时间 20 。

提示：

0 <= start < end <= 10⁹
每个测试用例，调用 book 方法的次数最多不超过 1000 次。

lightbulb

解题思路

方法一：有序集合

我们可以使用有序集合来存储日程安排，有序集合可以在 $O(\log n)$ 的时间内完成插入、删除、查找操作。有序集合中的元素，按照日程安排的 $\textit{endTime}$ 从小到大排序。

调用 $\text{book}(start, end)$ 方法时，我们在有序集合中查找第一个结束时间大于 $\textit{start}$ 的日程安排，如果存在并且其开始时间小于 $\textit{end}$ ，则说明存在重复预订，返回 $\text{false}$ ；否则，将 $\textit{end}$ 作为键，将 $\textit{start}$ 作为值插入有序集合中，返回 $\text{true}$ 。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为日程安排的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class MyCalendar:

    def __init__(self):
        self.sd = SortedDict()

    def book(self, start: int, end: int) -> bool:
        idx = self.sd.bisect_right(start)
        if idx < len(self.sd) and self.sd.values()[idx] < end:
            return False
        self.sd[end] = start
        return True


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

speed

复杂度分析

指标	值
时间	complexity is O(N log N) due to binary search for each booking in a list of N events. Space complexity is O(N) to store all booked intervals.
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
Consider the performance of repeated booking checks and how sorting or search impacts efficiency.
question_mark
Mention that using a sorted list plus binary search avoids checking all events linearly.
question_mark
Demonstrate understanding of half-open interval semantics to avoid off-by-one overlap errors.

warning

常见陷阱

外企场景

error
Failing to handle the half-open interval correctly, allowing end times to conflict with start times.
error
Performing linear scans for each booking, leading to O(N^2) behavior with many events.
error
Neglecting to check both neighboring intervals when inserting a new event in the sorted list.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Extending to My Calendar II or III, which allow one or multiple overlaps and require interval counting.
arrow_right_alt
Using a balanced binary search tree or segment tree instead of a list for faster dynamic insertions.
arrow_right_alt
Supporting queries for free time slots or event counts within a range instead of single bookings.

help

常见问题

外企场景

继续练习

#731 我的日程安排表 II #732 我的日程安排表 III #493 翻转对