Taro Logo

My Calendar II

Medium
Amazon logo
Amazon
1 view
Topics:
Arrays

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 startTime and endTime that represents a booking on the half-open interval [startTime, endTime), the range of real numbers x such that startTime <= x < 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.

Example:

Input
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]

Explanation
MyCalendarTwo myCalendarTwo = new MyCalendarTwo();
myCalendarTwo.book(10, 20); // return True, The event can be booked.
myCalendarTwo.book(50, 60); // return True, The event can be booked.
myCalendarTwo.book(10, 40); // return True, The event can be double booked.
myCalendarTwo.book(5, 15);  // return False, The event cannot be booked, because it would result in a triple booking.
myCalendarTwo.book(5, 10); // return True, The event can be booked, as it does not use time 10 which is already double booked.
myCalendarTwo.book(25, 55); // return True, The event can be booked, as the time in [25, 40) will be double booked with the third event, the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.

How would you implement this MyCalendarTwo class to handle bookings and avoid triple bookings?

Solution


Let's discuss how to implement a calendar that avoids triple bookings. We'll explore a naive approach and then a more optimized solution.

Naive Approach

The simplest approach is to maintain a list of bookings. When a new booking request arrives, we check it against all existing bookings to see if it causes a triple booking.

  1. Keep a list of all bookings (start, end).
  2. When a new booking (newStart, newEnd) comes in:
    • Iterate through all existing bookings.
    • Check for overlaps. If a triple booking occurs, return false. Otherwise, add the new booking.

Code (Python)

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

    def book(self, start, end):
        new_booking = (start, end)
        
        # Check for triple booking
        for i in range(len(self.bookings)):
            s1, e1 = self.bookings[i]
            overlap_start = max(start, s1)
            overlap_end = min(end, e1)
            if overlap_start < overlap_end:
                
                # Check overlap with other bookings for triple booking
                for j in range(len(self.bookings)):
                    if i == j: continue
                    s2, e2 = self.bookings[j]
                    overlap_start2 = max(overlap_start, s2)
                    overlap_end2 = min(overlap_end, e2)
                    if overlap_start2 < overlap_end2:
                        return False

        # No triple booking found, add the new booking
        self.bookings.append(new_booking)
        return True

Big O Analysis

  • Time Complexity: O(N2), where N is the number of bookings. For each new booking, we iterate through all existing bookings twice.
  • Space Complexity: O(N), to store the bookings.

Optimal Approach

A more efficient approach involves using two lists: one to store single bookings and another to store double bookings. This way, we can quickly identify overlaps that would result in triple bookings.

  1. Maintain two lists: single_bookings and double_bookings.
  2. When a new booking (newStart, newEnd) comes in:
    • Check for overlaps with double_bookings. If there's an overlap, return false (triple booking).
    • Check for overlaps with single_bookings. If overlaps are found, add those overlaps to double_bookings.
    • Add the new booking to single_bookings.

Code (Python)

class MyCalendarTwo:
    def __init__(self):
        self.single_bookings = []
        self.double_bookings = []

    def book(self, start, end):
        # Check for triple booking
        for s, e in self.double_bookings:
            if start < e and end > s:
                return False

        # Check for double booking, and create new double bookings
        for s, e in self.single_bookings:
            overlap_start = max(start, s)
            overlap_end = min(end, e)
            if overlap_start < overlap_end:
                self.double_bookings.append((overlap_start, overlap_end))

        # Add new single booking
        self.single_bookings.append((start, end))
        return True

Big O Analysis

  • Time Complexity: O(N), where N is the number of bookings. For each new booking, we iterate through double_bookings and single_bookings once.
  • Space Complexity: O(N), to store the single and double bookings.

Edge Cases

  • Empty Calendar: The calendar starts empty, so the first few bookings will always succeed.
  • Consecutive Bookings: Bookings that start immediately after another ends should be allowed.
  • Large Number of Bookings: The solution should scale reasonably well as the number of bookings increases.
  • Overlapping bookings covering the entire range of previous bookings: The overlapping checks need to accurately determine intersection points.