My Calendar Ii - Leetcode Solution

Problem statement:

Design a class to implement the following two functions:

• book(start, end) - book a new event with start and end time
• double_booked() - return True if there is any event that is double booked, else return False

A double booking is when two events overlap in time.

Solution:

We can use a modified version of the reservation system to keep track of the bookings. We can use an array of size 1000000001 (one more than the maximum value of end time) and initialize all values to 0. Whenever a new event is booked, we can increment the value of all indices corresponding to the event's start and end times. If a value of any index is greater than 1, it means that there is a double booking.

Code:

class MyCalendarTwo:
    def __init__(self):
        self.timeline = [0] * 1000000001

    def book(self, start: int, end: int) -> bool:
        for i in range(start, end):
            self.timeline[i] += 1
            if self.timeline[i] >= 3: # double booking
                # undo booking
                for j in range(start, i):
                    self.timeline[j] -= 1
                return False
        return True

    def double_booked(self) -> bool:
        for i in range(1000000001):
            if self.timeline[i] >= 2:
                return True
        return False

Explanation:

In the book function, we increment the values of the indices corresponding to the start and end times of the event. If at any point, the value of an index becomes greater than or equal to 3, it means that there is a double booking. In such a case, we undo the booking by decrementing the values of the indices corresponding to the start and end times of the event, and return False.

In the double_booked function, we simply loop through the entire timeline and check if any index has a value greater than or equal to 2, indicating a double booking.

Complexity analysis:

• book function inserts an element into the data structure (timeline) the number of elements from start to end. Hence, the time complexity of this function is O(N), where N is the duration of the event.
• double_booked function iterates over the entire timeline once, so its time complexity is also O(N).
• The space complexity of this solution is O(1), as the size of the timeline array is fixed.

1