My Calendar II

Medium

Asked by:

19 views

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 1:

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.

Constraints:

0 <= start < end <= 10⁹
At most 1000 calls will be made to book.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum number of events that will be added to the calendar?
Are the start and end times always integers, or can they be floating-point numbers?
Are the start and end times inclusive or exclusive? Specifically, does an event [a, b) include time 'a' but exclude 'b'?
If a new event causes more than double booking, should I simply return false, or should I modify the existing calendar to accommodate as much as possible before returning false?
What should I return if the start time is greater than or equal to the end time for an event being added?

Brute Force Solution

Approach

The brute force approach to the calendar problem is like checking every possible booking to see if there are more than two events overlapping. We will simulate each new booking and check it against all previous bookings. This involves exhaustively comparing each time slot with every other time slot.

Here's how the algorithm would work step-by-step:

When a new booking comes in, we first look at all the bookings that have already been made.
For the new booking, we go through each existing booking, one by one.
We see if the new booking overlaps with the current existing booking.
If they overlap, we note that intersection. If they don't, we move on to the next existing booking.
After comparing against all other bookings, we check all the noted intersections to see if any overlap with *each other*.
If any intersection overlaps with another intersection, it means three events overlap at that time, which is not allowed, so we reject the new booking.
If no intersections overlap, it means there are at most two events overlapping at any time, so we accept the new booking and add it to the list of bookings.

Code Implementation

class MyCalendarTwo:

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

    def book(self, start, end):
        new_booking = (start, end)
        intersections = []

        for existing_start, existing_end in self.bookings:
            # Find intersections of current booking with all existing bookings
            intersection_start = max(start, existing_start)
            intersection_end = min(end, existing_end)

            if intersection_start < intersection_end:
                intersections.append((intersection_start, intersection_end))

        # Check if any intersections overlap
        for i in range(len(intersections)):
            for j in range(i + 1, len(intersections)):
                first_start, first_end = intersections[i]
                second_start, second_end = intersections[j]

                overlap_start = max(first_start, second_start)
                overlap_end = min(first_end, second_end)

                # If triple booking occurs return false
                if overlap_start < overlap_end:
                    return False

        # Add the current booking to the schedule
        self.bookings.append(new_booking)

        return True

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through all existing bookings (let's say n bookings) for each new booking. Inside this outer loop, it iterates through all the identified intersections (potential double bookings) to check for triple bookings. In the worst case, the number of intersections could also be proportional to n. Thus, we have a nested loop structure where the outer loop runs up to n times and the inner loop also potentially runs up to n times in the worst case. This results in approximately n * n operations, which simplifies to O(n²).

Space Complexity

O(N^2) – The brute force approach stores existing bookings. With each new booking, intersections between the new booking and all existing bookings are noted, creating a list of intersection intervals. In the worst case, each new booking overlaps with all existing N bookings, resulting in N intersections. Subsequently, these N intersections are checked against each other for overlaps, which could potentially lead to storing up to N^2 intersection overlaps in the worst-case scenario. Therefore, the auxiliary space used to store these intersection intervals grows quadratically with the number of bookings N, leading to a space complexity of O(N^2).

Optimal Solution

Approach

The problem asks us to track how many bookings overlap at any given time. The key is to avoid checking every possible combination of bookings. Instead, we track the 'start' and 'end' times of each booking event and how they affect the overall overlap count.

Here's how the algorithm would work step-by-step:

Maintain a sorted list of all event start and end times.
For each new booking, add its start and end times to the sorted list.
As you go through the sorted list, keep track of how many events are currently happening.
Whenever you hit a start time, the current number of events increases by one.
Whenever you hit an end time, the current number of events decreases by one.
If, at any point, the current number of events is greater than two, it means there's a triple booking and you cannot add the new booking. Undo the addition.
If, after going through all events, the maximum overlap is never more than two, it means it is a valid booking, and you can add it permanently to your list of bookings.

Code Implementation

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

    def book(self, start_time, end_time):
        # Create a temporary booking to test for overlaps.
        temp_events = self.events + [(start_time, end_time, 1)]
        temp_events.sort(key=lambda x: x[0])

        overlap_count = 0
        for _, _, booking_type in temp_events:
            overlap_count += booking_type
            # Check if triple booking occurs in the temp booking
            if overlap_count > 2:
                return False

        # Mark start times with +1 and end times with -1.
        self.events.append((start_time, end_time, 1))
        self.events.append((end_time, start_time, -1))

        # Maintain sorted order by start time.
        self.events.sort(key=lambda x: x[0])

        return True

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each new booking attempt. For each attempt, it potentially inserts two new events (start and end) into a sorted list of existing events. The insertion into a sorted list of size n takes O(n) time (specifically, a linear time insertion to maintain the sorted order, in the worst-case using list.insert() as opposed to a binary search tree-based insertion). After the insertion, the algorithm iterates through the entire sorted list of events to check the maximum overlap count, which takes O(n) time. Since these two O(n) operations are performed within the loop of n booking attempts, the overall time complexity is O(n * (n + n)), which simplifies to O(n²).

Space Complexity

O(N) – The space complexity is dominated by the sorted list of event start and end times. In the worst case, each booking will add two entries (start and end) to this list. If we have N bookings, the list can grow to a size of 2N. Thus, the auxiliary space required is proportional to N, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty input	Return true since an empty calendar has no conflicts.
Single event added	The single event should be added without conflict, and return true.
Events that completely overlap	The algorithm needs to correctly identify the overlapping interval length exceeding 2.
Events that partially overlap	The algorithm needs to accurately determine the overlapping interval and check the number of events overlapping it.
A large number of events are added to calendar	The algorithm's time complexity should be efficient, potentially using a sorted data structure or a segment tree, to handle many events effectively.
Events with identical start and end times	Treat these as valid events, and accurately count the number of overlapping intervals.
Integer overflow when calculating overlaps (very large start/end times)	Consider using long integers or a similar data type to prevent overflow during interval calculations and comparisons.
Events added in reverse sorted order, or in random unsorted order	The algorithm should function correctly regardless of the order in which events are added, by correctly identifying overlaps.

Null or empty input

How to Handle:

Return true since an empty calendar has no conflicts.

Single event added

How to Handle:

The single event should be added without conflict, and return true.

Events that completely overlap

How to Handle:

The algorithm needs to correctly identify the overlapping interval length exceeding 2.

Events that partially overlap

How to Handle:

The algorithm needs to accurately determine the overlapping interval and check the number of events overlapping it.

A large number of events are added to calendar

How to Handle:

The algorithm's time complexity should be efficient, potentially using a sorted data structure or a segment tree, to handle many events effectively.

Events with identical start and end times

How to Handle:

Treat these as valid events, and accurately count the number of overlapping intervals.

Integer overflow when calculating overlaps (very large start/end times)

How to Handle:

Consider using long integers or a similar data type to prevent overflow during interval calculations and comparisons.

Events added in reverse sorted order, or in random unsorted order

How to Handle:

The algorithm should function correctly regardless of the order in which events are added, by correctly identifying overlaps.