My Calendar II — LeetCode 731 Python Solution

The problem

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a triple booking.

Example

Input

["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]

Output

[null, true, true, true, false, true, true]

Explanation

MyCalendarTwo myCalendarTwo = new MyCalendarTwo();

Python solution

class MyCalendarTwo:

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

    def book(self, startTime: int, endTime: int) -> bool:
        self.sd[startTime] = self.sd.get(startTime, 0) + 1
        self.sd[endTime] = self.sd.get(endTime, 0) - 1
        s = 0
        for v in self.sd.values():
            s += v
            if s > 2:
                self.sd[startTime] -= 1
                self.sd[endTime] += 1
                return False
        return True


# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(startTime,endTime)

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 731. My Calendar II 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.

Related problems