Leetcode Daily Question 27/09/2024 - 731. My Calendar II

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 triple booking. A triple booking happens when three events have some non-empty intersection (i.e., some moment is common to all the three 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 MyCalendarTwo class: MyCalendarTwo() 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 triple booking. Otherwise, return false and do not add the event to the calendar.

class MyCalendarTwo:
  def __init__(self):
    self.calendar = []
    self.overlaps = []
    
  def book(self, start:int, end: int) -> bool:
    calendar = self.calendar
    overlaps = self.overlaps
    for o_start, o_end in overlaps:
      if start < o_end and end > o_start:
        return False
    
    for c_start, c_end in calendar:
      if start < c_end and end > c_start:
        overlap_start = max(start, c_start)
        overlap_end = min(end, c_end)
        overlaps.append((overlap_start, overlap_end))
    calendar.append((start,end))
    return True

Explanation:

This is similar to yesterday's question. Instead of preventing interval to overlap, we allow overlap once.

To do this, we keep track of all the overlapped intervals and compare to our input to check if a triple intersection exists.

We then update the overlap array as well as the calendar array.

def __init__(self):
  self.calendar = []
  self.overlaps = []
  
def book(self, start: int, end: int) -> bool:
  calendar = self.calendar
  overlaps = self.overlaps
  
  for o_start, o_end in overlaps:
    if start < o_end and end > o_start:
      return False
    
  for c_start, c_end in calendar:
    if end > c_start and start < c_end:
      overlap_start = max(start, c_start)
      overlap_end = min(end, c_end)
      overlaps.append((overlap_start, overlap_end))
  
  calendar.append((start,end))
  return True

The time complexity is O(n) as we need to iterate through calendar which has worst case O(n).

The space complexity is O(n) as we need to store all valid bookings in calendar which has worst case O(n).

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