How hard is LeetCode 732. My Calendar III?

LeetCode 732. My Calendar III is rated Hard on LeetCode.

What is the time complexity of LeetCode 732. My Calendar III?

The Python solution on this page runs in O(n \times \log n).

What is the space complexity of LeetCode 732. My Calendar III?

The Python solution on this page uses O(n), where n is the number of bookings auxiliary space.

What topics does LeetCode 732. My Calendar III cover?

LeetCode 732. My Calendar III is tagged Design, Segment Tree, Binary Search, Ordered Set and Prefix Sum on LeetCode.

My Calendar III — LeetCode 732 Python Solution

HardDesignSegment TreeBinary SearchOrdered SetPrefix Sum

Problem: #732
Pattern: Prefix Sum
Reading time: 13 min
Source: leetcode.com

The problem

A k-booking happens when k events have some non-empty intersection (i.e., there is some time that is common to all k events.) You are given some events [startTime, endTime), after each given event, return an integer k representing the maximum k-booking between all the previous events. Implement the MyCalendarThree class: MyCalendarThree() Initializes the object.

Example

Input: ["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
Output: [null, 1, 1, 2, 3, 3, 3]
Explanation: MyCalendarThree myCalendarThree = new MyCalendarThree();

Python solution

Python

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)

Complexity

Measure	Complexity
Time	O(n \times \log n)
Space	O(n), where n is the number of bookings auxiliary

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 732. My Calendar III is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 732. My Calendar III?: LeetCode 732. My Calendar III is rated Hard on LeetCode.
What is the time complexity of LeetCode 732. My Calendar III?: The Python solution on this page runs in O(n \times \log n).
What is the space complexity of LeetCode 732. My Calendar III?: The Python solution on this page uses O(n), where n is the number of bookings auxiliary space.
What topics does LeetCode 732. My Calendar III cover?: LeetCode 732. My Calendar III is tagged Design, Segment Tree, Binary Search, Ordered Set and Prefix Sum on LeetCode.