We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

My Calendar II

Number: 731

Difficulty: Medium

Paid? No

Companies: Amazon, Uber, Google

Problem Description

Design a calendar system that supports booking events without causing a triple booking. A triple booking occurs when three events overlap at any time point. Each event is represented as an interval [start, end), and an event is allowed if its addition does not make any time point have three or more overlapping events.

Key Insights

  • Maintain two separate collections: one for all booked events and one for the periods that are already double booked.
  • When booking a new event, first check if it conflicts with any of the double booked intervals. If it does, adding the event would create a triple booking.
  • Otherwise, for every existing event, compute and record any new overlap created by the new event with that event. These overlaps form the new double booking intervals.
  • Finally, add the new event to the collection of all bookings.

Space and Time Complexity

Time Complexity: O(n) per booking call in the worst case, where n is the number of events booked so far. Space Complexity: O(n) to store all the bookings and overlaps.

Solution

We use a two-list approach:

  1. A list (or array) to record all booked events.
  2. A list (or array) to record all intervals where double bookings have occurred.

For each new event:

  • First check the new event interval against all intervals in the second list (overlaps). If any overlap exists, then a triple booking would occur, and we return false.
  • Otherwise, for each event already booked, if there is an overlap with the new event, compute that overlapping interval and add it to the overlaps list.
  • Finally, add the new event to the booked events list and return true.

This approach leverages the idea of interval intersection and simple linear scans over the events. The challenge lies in correctly computing the overlapping intervals and ensuring that triple overlaps are not introduced.

Code Solutions

# Python implementation of MyCalendarTwo
class MyCalendarTwo:
    def __init__(self):
        # List to store all the booked events
        self.booked = []
        # List to store all the double-booked intervals (overlaps)
        self.overlaps = []

    def book(self, start: int, end: int) -> bool:
        # Check if new event overlaps with any double-booked interval.
        for os, oe in self.overlaps:
            # If there's any overlap with a double-booked interval, triple booking occurs.
            if start < oe and end > os:
                return False
        
        # For all previously booked events, check if they overlap with the new event.
        for bs, be in self.booked:
            if start < be and end > bs:
                # Calculate the overlapping segment and record it as a double booking.
                self.overlaps.append((max(start, bs), min(end, be)))
        
        # Add the new event to the booked list as it doesn't cause a triple booking.
        self.booked.append((start, end))
        return True

# Example usage:
# myCalendar = MyCalendarTwo()
# print(myCalendar.book(10, 20))  # True
# print(myCalendar.book(50, 60))  # True
# print(myCalendar.book(10, 40))  # True
# print(myCalendar.book(5, 15))   # False
← Back to All Questions