Problem of The Day: My Calendar II

Problem Statement

from datetime import datetime

Intuition

My initial intuition is to use a list to keep track of all the bookings. For every new booking, we check for any overlaps with the existing bookings. If an overlap is found, it is stored temporarily and further checks are made to ensure that the new booking does not result in a triple booking.

Approach

1. I maintain a list called calendar to keep track of all the bookings.
2. For each new booking, I check against all the existing bookings to find overlaps.
3. If the overlap results in a triple booking, I return False.
4. If no triple booking is found, I add the new booking to the calendar list and return True.

Complexity

• Time complexity: The time complexity is \(O(n^2)\) in the worst case scenario, where n is the number of bookings. This is because, for each new booking, we potentially check all previous bookings for overlaps.

• Space complexity: The space complexity is \(O(n)\) since we store all the bookings in a list.

Code

class MyCalendarTwo:

    def __init__(self):
        self.calendar = []

    def book(self, start: int, end: int) -> bool:
        if not self.calendar:
            self.calendar.append([start, end])
            return True

        overlaps = []
        for booked_start, booked_end in self.calendar:
            if booked_start <= start < booked_end or booked_start < end <= booked_end or (start <= booked_start and end >= booked_end):
                interval = [max(booked_start, start), min(booked_end, end)]
                if interval not in overlaps:
                    overlaps.append(interval)
                else:
                    return False

        for i in range(1, len(overlaps)):
            prev_start, prev_end = overlaps[i - 1]
            curr_start, curr_end = overlaps[i]
            if curr_start < prev_end or prev_end > curr_start:
                return False

        self.calendar.append([start, end])
        self.calendar.sort()
        return True


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

Editorial

Approach 1: Using Overlapped Intervals

class MyCalendarTwo:

    def __init__(self):
        self.bookings = []
        self.overlap_bookings = []

    def book(self, start: int, end: int) -> bool:
        # Check if the new booking overlaps with any double-booked booking.
        for booking in self.overlap_bookings:
            if self.does_overlap(booking[0], booking[1], start, end):
                return False

        # Add any new double overlaps that the current booking creates.
        for booking in self.bookings:
            if self.does_overlap(booking[0], booking[1], start, end):
                self.overlap_bookings.append(
                    self.get_overlapped(booking[0], booking[1], start, end)
                )

        # Add the new booking to the list of bookings.
        self.bookings.append((start, end))
        return True

    # Return True if the booking [start1, end1) & [start2, end2) overlaps.
    def does_overlap(
        self, start1: int, end1: int, start2: int, end2: int
    ) -> bool:
        return max(start1, start2) < min(end1, end2)

    # Return the overlapping booking between [start1, end1) & [start2, end2).
    def get_overlapped(
        self, start1: int, end1: int, start2: int, end2: int
    ) -> tuple:
        return max(start1, start2), min(end1, end2)

• time: O(n)
• space: O(n)

Approach 2: Line Sweep

from sortedcontainers import SortedDict


class MyCalendarTwo:

    def __init__(self):
        # Store the number of bookings at each point.
        self.booking_count = SortedDict()
        # The maximum number of overlapped bookings allowed.
        self.max_overlapped_booking = 2

    def book(self, start: int, end: int) -> bool:
        # Increase and decrease the booking count at the start and end respectively.
        self.booking_count[start] = self.booking_count.get(start, 0) + 1
        self.booking_count[end] = self.booking_count.get(end, 0) - 1

        overlapped_booking = 0

        # Calculate the prefix sum of bookings.
        for count in self.booking_count.values():
            overlapped_booking += count
            # If the number of overlaps exceeds the allowed limit
            # rollback and return False.
            if overlapped_booking > self.max_overlapped_booking:
                # Rollback changes.
                self.booking_count[start] -= 1
                self.booking_count[end] += 1

                # Remove entries if their count becomes zero to clean up the SortedDict.
                if self.booking_count[start] == 0:
                    del self.booking_count[start]

                return False

        return True

• time: O(n log n)
• space: O(n)