#732

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

My Calendar III

Implement My Calendar III to track maximum overlapping events efficiently using binary search and segment tree techniques for high-volume queries.

binary search design segment tree prefix sum ordered set

Problem Statement

Design a MyCalendarThree class that can store event intervals and report the maximum number of overlapping events (k-booking) dynamically. Each event is represented as a half-open interval [startTime, endTime), where 0 <= startTime < endTime <= 10^9.

After each booking, return the highest k such that k events overlap at some moment. Implement the book method to accept a new interval, update the internal state, and return the current maximum k-booking for all added intervals.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["MyCalendarThree", "book", "book", "book", "book", "book", "book"] [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]] Output [null, 1, 1, 2, 3, 3, 3]

Explanation MyCalendarThree myCalendarThree = new MyCalendarThree(); myCalendarThree.book(10, 20); // return 1 myCalendarThree.book(50, 60); // return 1 myCalendarThree.book(10, 40); // return 2 myCalendarThree.book(5, 15); // return 3 myCalendarThree.book(5, 10); // return 3 myCalendarThree.book(25, 55); // return 3

Constraints

0 <= startTime < endTime <= 109
At most 400 calls will be made to book.

Solution Approach

Binary Search Over the Answer Space

Treat each interval as start and end events, and use a sorted list to simulate active overlaps. Apply binary search to determine if a proposed k-booking is achievable, iteratively refining the maximum value.

Segment Tree Counting

Implement a segment tree to track event additions and range increments efficiently. Each booking updates relevant nodes, and querying the root returns the current maximum overlap, aligning with the k-booking requirement.

Prefix Sum Sweep Line

Convert all start and end times into events with +1 for start and -1 for end. Sort them and traverse cumulatively to maintain a running overlap count. The maximum encountered count represents the maximum k-booking at any time.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time 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.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Segment Tree

A segment tree divides the entire interval into multiple non-contiguous subintervals, with the number of subintervals not exceeding $\log(\text{width})$. To update the value of an element, we only need to update $\log(\text{width})$ intervals, and these intervals are all contained within a larger interval that includes the element. When modifying intervals, we use **lazy propagation** to ensure efficiency.

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

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)

Continue Practicing

#731 my calendar ii #729 my calendar i #715 range module