What is the main challenge in My Calendar III?

The challenge is efficiently tracking the maximum number of overlapping intervals dynamically as new bookings are added.

How does the binary search pattern apply here?

Binary search over the valid answer space helps test if a certain k-booking is possible, refining the maximum efficiently.

Can sweep line solve this problem?

Yes, converting start and end times into +1/-1 events and processing in order provides the correct maximum overlap count.

Why not use a simple list scan for bookings?

A naive scan can be too slow for 400 bookings with large time ranges, leading to timeouts in practice.

Is segment tree always better than prefix sum here?

Segment tree is more efficient when time points are sparse and dynamic range queries are needed, while prefix sum suffices for denser or smaller ranges.

#732

Hard

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

LeetCode 题解工作台

我的日程安排表 III

当 k 个日程存在一些非空交集时（即, k 个日程包含了一些相同时间），就会产生 k 次预订。给你一些日程安排 [startTime, endTime) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。实现一个 MyCalendarThree 类来存…

二分查找设计线段树前缀和有序集合

题目描述

当 k 个日程存在一些非空交集时（即, k 个日程包含了一些相同时间），就会产生 k 次预订。

给你一些日程安排 [startTime, endTime) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。

实现一个 MyCalendarThree 类来存放你的日程安排，你可以一直添加新的日程安排。

MyCalendarThree() 初始化对象。
int book(int startTime, int endTime) 返回一个整数 k ，表示日历中存在的 k 次预订的最大值。

示例：

输入：
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
输出：
[null, 1, 1, 2, 3, 3, 3]

解释：
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // 返回 1 ，第一个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(50, 60); // 返回 1 ，第二个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(10, 40); // 返回 2 ，第三个日程安排 [10, 40) 与第一个日程安排相交，所以最大 k 次预订是 2 次预订。
myCalendarThree.book(5, 15); // 返回 3 ，剩下的日程安排的最大 k 次预订是 3 次预订。
myCalendarThree.book(5, 10); // 返回 3
myCalendarThree.book(25, 55); // 返回 3

提示：

0 <= startTime < endTime <= 10⁹
每个测试用例，调用 book 函数最多不超过 400次

lightbulb

解题思路

方法一：线段树

线段树将整个区间分割为多个不连续的子区间，子区间的数量不超过 $log(\text{width})$ 。更新某个元素的值，只需要更新 $log(\text{width})$ 个区间，并且这些区间都包含在一个包含该元素的大区间内。区间修改时，需要使用懒标记保证效率。

线段树的每个节点代表一个区间；
线段树具有唯一的根节点，代表的区间是整个统计范围，如 $[1,N]$ ；
线段树的每个叶子节点代表一个长度为 $1$ 的元区间 $[x, x]$ ；
对于每个内部节点 $[l,r]$ ，它的左儿子是 $[l,\text{mid}]$ ，右儿子是 $[\text{mid}+1,r]$ , 其中 $\text{mid} = ⌊(l+r)/2⌋$ (即向下取整)。

对于本题，线段树节点维护的信息有：

区间范围内被预定的次数的最大值 $v$
懒标记 $\text{add}$

由于时间范围为 $10^9$ ，非常大，因此我们采用动态开点。

时间复杂度 $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

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

class Node:
    def __init__(self, l, r):
        self.left = None
        self.right = None
        self.l = l
        self.r = r
        self.mid = (l + r) >> 1
        self.v = 0
        self.add = 0


class SegmentTree:
    def __init__(self):
        self.root = Node(1, int(1e9 + 1))

    def modify(self, l: int, r: int, v: int, node: Node = None):
        if l > r:
            return
        if node is None:
            node = self.root
        if node.l >= l and node.r <= r:
            node.v += v
            node.add += v
            return
        self.pushdown(node)
        if l <= node.mid:
            self.modify(l, r, v, node.left)
        if r > node.mid:
            self.modify(l, r, v, node.right)
        self.pushup(node)

    def query(self, l: int, r: int, node: Node = None) -> int:
        if l > r:
            return 0
        if node is None:
            node = self.root
        if node.l >= l and node.r <= r:
            return node.v
        self.pushdown(node)
        v = 0
        if l <= node.mid:
            v = max(v, self.query(l, r, node.left))
        if r > node.mid:
            v = max(v, self.query(l, r, node.right))
        return v

    def pushup(self, node: Node):
        node.v = max(node.left.v, node.right.v)

    def pushdown(self, node: Node):
        if node.left is None:
            node.left = Node(node.l, node.mid)
        if node.right is None:
            node.right = Node(node.mid + 1, node.r)
        if node.add:
            node.left.v += node.add
            node.right.v += node.add
            node.left.add += node.add
            node.right.add += node.add
            node.add = 0


class MyCalendarThree:
    def __init__(self):
        self.tree = SegmentTree()

    def book(self, start: int, end: int) -> int:
        self.tree.modify(start + 1, end, 1)
        return self.tree.query(1, int(1e9 + 1))


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

speed

复杂度分析

指标	值
时间	complexity depends on the approach: sweep line with sorting is O(N log N), segment tree can achieve O(N log M) where M is the number of distinct time points. Space complexity is O(N) for events storage or O(M) for segment tree nodes.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Asks about handling large time ranges efficiently.
question_mark
Mentions potential overlapping edge cases like fully nested intervals.
question_mark
Questions the trade-off between direct simulation and segment tree efficiency.

warning

常见陷阱

外企场景

error
Neglecting the half-open interval semantics leading to off-by-one errors.
error
Assuming a simple list scan is fast enough for 400 bookings, causing timeouts.
error
Not updating both start and end counts, missing maximum k-booking correctly.

swap_horiz

进阶变体

外企场景

arrow_right_alt
My Calendar II: track double bookings only, simpler overlap counting.
arrow_right_alt
Counting overlaps with dynamic interval insertion and deletion, requiring interval trees.
arrow_right_alt
Generalized maximum overlap queries over multiple calendars for real-time scheduling.

help

常见问题

外企场景

继续练习

#731 我的日程安排表 II #729 我的日程安排表 I #715 Range 模块