Problem of The Day: My Calendar I

Problem Statement

Intuition

The idea is to maintain a list of already booked intervals and check for any overlap with the new booking request. If the new interval overlaps with any of the existing intervals, we should reject the booking. Otherwise, we add the new interval to our list of booked intervals.

Approach

1. We maintain an array arr to store all booked intervals as pairs of [start, end].
2. For each new booking request, we iterate through the arr to check if it overlaps with any of the existing bookings.
   • An overlap occurs if end > booked_start and start < booked_end.
3. If there is no overlap with any existing booking, we add the new booking interval to arr and return True.
4. If there is an overlap, we return False.
5. Finally, we sort the array arr to keep the intervals in order, although this step is optional for correctness.

Complexity

• Time complexity:

  • For each booking request, we check all existing bookings in the worst case, which is \(O(n)\), where n is the number of bookings made so far. Sorting the array costs \(O(n \log n)\), but it’s optional.

• Space complexity:

  • We store all the bookings in a list, so the space complexity is \(O(n)\), where n is the number of bookings.

Code

class MyCalendar:

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

    def book(self, start: int, end: int) -> bool:
        if self.arr:
            for booked_start, booked_end in self.arr:
                if end <= booked_start:
                    continue
                if start >= booked_end:
                    continue
                return False
        self.arr.append([start, end])
        self.arr.sort()
        return True


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

Editorial

Approach #1: Brute Force

class MyCalendar:

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

    def book(self, start, end):
        for s, e in self.calendar:
            if s < end and start < e:
                return False
        self.calendar.append((start, end))
        return True

• time: O(N^2)
• space: O(N)

Approach #2: Sorted List + Binary Search

from sortedcontainers import SortedList

class MyCalendar:
    def __init__(self):
        self.calendar = SortedList()

    def book(self, start: int, end: int) -> bool:
        idx = self.calendar.bisect_right((start, end))
        if (idx > 0 and self.calendar[idx-1][1] > start) or (idx < len(self.calendar) and self.calendar[idx][0] < end):
            return False
        self.calendar.add((start, end))
        return True

• time: O(NLogN)
• space: O(N)