Naive Solution

A brute force approach would involve storing all the bookings as intervals and, for each new booking, checking for triple bookings by iterating through all possible combinations of three intervals (including the new one) and checking if they overlap. This is inefficient but conceptually simple.

Algorithm

1. Store bookings in a list of (start, end) tuples.
2. When book(start, end) is called:
   • Add the new booking to the list of bookings.
   • Iterate through all combinations of three bookings. If there are n bookings in the list, this will take O(n^3) time.
   • For each combination, check if the intervals intersect. Intervals intersect if max(start1, start2, start3) < min(end1, end2, end3). If they intersect, return false and remove the newly added booking.
   • If no triple booking is found, return true.

Code (Python)

class MyCalendarTwo:
    def __init__(self):
        self.bookings = []

    def book(self, start: int, end: int) -> bool:
        self.bookings.append((start, end))
        n = len(self.bookings)
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    s1, e1 = self.bookings[i]
                    s2, e2 = self.bookings[j]
                    s3, e3 = self.bookings[k]
                    if max(s1, s2, s3) < min(e1, e2, e3):
                        self.bookings.pop()
                        return False
        return True

Time Complexity

O(n^3) for each call to book, where n is the number of bookings.

Space Complexity

O(n), where n is the number of bookings, to store the list of intervals.

Optimal Solution: Using Overlap Counts

A more efficient approach involves tracking the number of overlaps at any given time using two lists: one for single bookings and one for double bookings.

Algorithm

1. Maintain two lists: single_bookings and double_bookings.
2. When book(start, end) is called:
   • Check for intersection with existing double_bookings. If the new interval intersects with any interval in double_bookings, it means there will be a triple booking. In that case, return false.
   • Otherwise, check for intersection with existing single_bookings. If there is an intersection, add the intersection interval to double_bookings.
   • Finally, add the new booking to single_bookings.

Code (Python)

class MyCalendarTwo:
    def __init__(self):
        self.single_bookings = []
        self.double_bookings = []

    def book(self, start: int, end: int) -> bool:
        for s, e in self.double_bookings:
            if start < e and end > s:
                return False

        for s, e in self.single_bookings:
            intersection_start = max(start, s)
            intersection_end = min(end, e)
            if intersection_start < intersection_end:
                self.double_bookings.append((intersection_start, intersection_end))

        self.single_bookings.append((start, end))
        return True

Time Complexity

O(n) for each call to book, where n is the number of existing bookings, due to iterating through single_bookings and double_bookings.

Space Complexity

O(n), where n is the number of bookings, to store single_bookings and double_bookings.

Edge Cases

• Empty Calendar: When the calendar is initially empty, the first booking should always succeed.
• Adjacent Bookings: Bookings that are adjacent (e.g., [10, 20] and [20, 30]) should be allowed as they do not overlap.
• Overlapping Bookings: Overlapping bookings need to be handled carefully to ensure that triple bookings are correctly identified.
• Large Number of Bookings: The solution should scale efficiently as the number of bookings increases.