My Calendar I

Medium

Uber

11 views

Topics:

ArraysBinary Search

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.

A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both 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 MyCalendar class:

MyCalendar() 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 double booking. Otherwise, return false and do not add the event to the calendar.

Example 1:

Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]

Explanation
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.

Constraints:

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

My Calendar I

Medium

Uber

11 views

Topics:

ArraysBinary Search

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.

A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both 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 MyCalendar class:

MyCalendar() 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 double booking. Otherwise, return false and do not add the event to the calendar.

Example 1:

Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]

Explanation
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.

Constraints:

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

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 are the possible ranges for the start and end times? Are they integers?
Is it possible for start and end times to be equal (i.e., zero-length event)?
If a new event's end time is equal to an existing event's start time, should it be considered a conflict?
How many events should the `MyCalendar` class handle, roughly? Should I optimize for a specific number of calls to the `book` function?
Can I assume the input start time will always be strictly less than the end time?

Brute Force Solution

Approach

The brute force approach for the calendar problem involves checking every possible arrangement. We consider each new event and see if it conflicts with any of the events we've already added to the calendar. If there is no conflict, we add it; otherwise, we reject it.

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

When a new event comes in, compare it to every single event that is already on the calendar.
For each existing event, check if the new event's time overlaps with it at all.
If the new event overlaps with even one existing event, then the new event cannot be added to the calendar.
If the new event does not overlap with any of the existing events, then it can be added to the calendar.

Code Implementation

class MyCalendar:

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

    def book(self, start_time, end_time) -> bool:
        # Check if the new event overlaps with any existing events
        for existing_start_time, existing_end_time in self.calendar:
            if start_time < existing_end_time and end_time > existing_start_time:

                # If overlap found, the event can't be booked
                return False

        # No overlap found, book the event
        self.calendar.append((start_time, end_time))

        # Always maintain sorted calendar for optimization
        self.calendar.sort()
        return True

# Your MyCalendar object will be instantiated and called as such:
# myCalendar = MyCalendar()
# param_1 = myCalendar.book(start,end)

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The MyCalendar I solution, using the described approach, checks for overlap with existing events. In the worst case, we have n events in the calendar already. When adding a new event, we iterate through all n existing events to check for overlaps. Therefore, for each of the n potential insertions, we perform n overlap checks, leading to approximately n * n operations, simplifying to O(n²).

Space Complexity

O(N) – The brute force approach stores existing events in the calendar. As each new event is added to the calendar if it doesn't overlap with existing events, the size of the calendar grows. In the worst case, all N events are added to the calendar. Therefore, the auxiliary space required to store these events grows linearly with the number of events, N.

Optimal Solution

Approach

The optimal strategy to solve the My Calendar I problem is to keep your existing bookings sorted. Then, when a new booking comes in, you only need to check if it overlaps with any of the existing ones. If it doesn't, you can add it to the sorted list of bookings.

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

Start by storing existing bookings in a way that keeps them in order based on their start time.
When a new booking is requested, compare it with the existing bookings.
For each existing booking, check if the new booking overlaps with it. Overlap means they share some time.
If the new booking doesn't overlap with any existing booking, then the new booking is valid.
If the new booking is valid, add it to your stored list of bookings, making sure to keep the list in sorted order.
If the new booking overlaps with any existing booking, then the new booking is not valid, and you cannot add it.

Code Implementation

class MyCalendar:

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

    def book(self, start_time, end_time):
        # Iterate through existing bookings to check for overlaps.
        for existing_start_time, existing_end_time in self.bookings:
            if start_time < existing_end_time and end_time > existing_start_time:
                return False

            # If no overlap is found, insert the new booking into the sorted list.
        self.bookings.append((start_time, end_time))
        self.bookings.sort()
        
        return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through a list of existing bookings. With each new booking request, it compares the new booking against all existing bookings to check for overlaps. This check involves iterating through the existing bookings (n bookings in the worst case). In the worst case, we might add 'n' bookings, so for each booking, we potentially compare it against all other bookings resulting in approximately n * n/2 comparisons. Therefore, the time complexity is O(n²).

Space Complexity

O(N) – The described solution maintains a sorted list of existing bookings. In the worst-case scenario, we might store all N bookings, where N is the number of calls to the 'book' function. Therefore, the space used by the sorted list scales linearly with the number of bookings. No other significant auxiliary space is used.

Edge Cases

Case	How to Handle
First event to be added to the calendar (empty calendar).	The algorithm should add it directly as there are no existing events to conflict with.
New event completely overlaps an existing event.	The solution must correctly identify this overlap and return false.
New event is completely contained within an existing event.	The solution must correctly identify this overlap and return false.
New event starts at the exact end time of an existing event (adjacent).	This should be considered a valid booking as there's no overlap.
New event ends at the exact start time of an existing event (adjacent).	This should be considered a valid booking as there's no overlap.
Extremely large start and end values (close to integer limits).	Ensure integer overflow is avoided when calculating overlaps.
Adding a large number of events, testing scalability.	The chosen data structure (e.g., sorted list or binary search tree) should provide efficient lookup to maintain reasonable booking time complexity.
Multiple existing events that are very close together or overlapping on boundaries.	The algorithm should iterate through all relevant existing events to determine if the new event conflicts with any.