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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

My Calendar II

Difficulty: Medium

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. The event can be represented as a pair of integers startTime and endTime that represents a booking on the half-open interval [startTime, endTime).

Implement the MyCalendarTwo class:

  • MyCalendarTwo() Initializes the calendar object.
  • boolean book(int startTime, int endTime) 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.

Key Insights

  • We need to track overlapping intervals for events to prevent triple bookings.
  • A simple count of overlapping events is needed to determine if a new booking would cause a triple booking.
  • Efficiently managing overlapping intervals can be achieved using a data structure that allows quick updates and queries.

Space and Time Complexity

Time Complexity: O(n log n) for inserting and checking overlaps due to sorting operations on the intervals.

Space Complexity: O(n) for storing the booked intervals.

Solution

To solve this problem, we can use a list to maintain the start and end times of the events. When a new booking is requested, we will:

  1. Check for overlaps with existing bookings by iterating through the list of booked intervals.
  2. Maintain a count of how many events are overlapping at any given time.
  3. If at any point the count exceeds 2, we will reject the booking.
  4. If the booking is valid, we add it to our list of booked intervals.

We can also utilize a dictionary to keep track of the number of overlapping events at each time point.

Code Solutions

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

    def book(self, start: int, end: int) -> bool:
        # Check for overlapping events
        count = 0
        for s, e in self.booked:
            if start < e and s < end:  # there's an overlap
                count += 1
                if count == 2:  # already double booked
                    break

        if count >= 2:
            return False  # triple booking

        # If it is valid, add the event to booked
        self.booked.append((start, end))
        return True
← Back to All Questions