Leetcode Daily Question 26/09/2024 - 729. My Calendar I

Problem Description:

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking. A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.). The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end. Implement the MyCalendar class: MyCalendar() Initializes the calendar object. boolean book(int start, int end) Returns true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

class MyCalendar:
  def __init__(self):
    self.calendar = [(-1,-1), (float('inf'), float('inf'))]
  
  
  def book(self, start: int, end: int) -> bool:
    calendar = self.calendar
    index = bisect.bisect_left(calendar, (start,end))
    if start < calendar[index - 1][1] or end > calendar[index][0]:
      return False
   	calendar.insert(index, (start, end))
    return True

Explanation:

We can solve this by keeping a sorted list of valid bookings, finding the insert point of this new potential booking, and checking the start and end points agains its neighbour to see if it is valid.

A good way is to use python's in-built bisect module. There are two main methods in this module, bisect_left and bisect_right. Bisect_left finds the left most insertion point of an element without disturbing the order of the sorted list. Bisect_right finds the right most insertion point of an element without disturbing the order of the sorted list.

Here are some examples. Suppose in the calendar you already have [(-1,-1), (8,13), (18,26), (float('inf'), float('inf'))].
You want to check if (9, 20), (12,17) are valid bookings.

Both of them should fit between (8,13) and (18,26). Let us compare the start and end points of our target (9,20) with these.

We see that since end = 20 > 18, this is not valid. Similarly, since start = 12 < 13, this is not valid.

So we can see we only need to check if the start point of your booking sits between the start and end point of your previous booking, or if your end point sits between the start and end of the next booking.

If we complete these steps without fail, then we can insert the booking and return True.

# Initiate object with self.calendar = []
def book(start, end):
  calendar = self.calendar # Make the calendar easier to call
  index = bisect.bisect_left(calendar, (start, end))
  
  if start < calender[index - 1][1] or end > calendar[index][0]:
    return False
  
  calendar.insert(index, (start, end))
  return True

The time complexity is O(n). The bisect function is a binary search, so it takes O(log n) time. However, the insertion requires the shifting of elements, so the worst case is O(n).

The space complexity is O(n) as we could potentially store all input bookings.

The full solution can be found near the top of the page.