731. My Calendar II

Problem Description

In this problem, you are tasked with creating a calendar system that can add new events without creating a situation wherein three events overlap in time—this is what is referred to as a "triple booking." Events are defined by their start and end times, with the start time being inclusive and the end time being exclusive, signified by the interval [start, end). The problem requires the implementation of a class, MyCalendarTwo, which provides two functionalities:

1. Initializing the calendar object.
2. Booking an event (specified by its start and end) if doing so does not result in any triple booking. It returns true if the event can be added without a triple booking, otherwise false.

The objective is to efficiently manage a calendar by keeping track of events while ensuring at most two events may overlap, but not three. This requires careful tracking of each event's start and end times.

Intuition

The intuition behind the solution comes from the need to manage the overlaps efficiently. Given that double bookings are allowed but not triple bookings, we need to track whenever an event starts and ends, and how this impacts the existing timeline of bookings. Here, we can use a data structure such as the SortedDict from the sortedcontainers module which keeps the keys sorted and allows us to efficiently determine starting and ending points of events.

The approach is to increment the count at the event start time and decrement it at the event end time. Every time we attempt to book an event, we update the timeline with the start and end times. After adding the event to the calendar, we iterate through all time points in our SortedDict and maintain a running sum that represents the current number of overlapping events. If, at any time, this sum exceeds 2, it means we are trying to create a triple booking, which is not allowed. At this point, we need to revert this booking by decrementing the count at the start time and incrementing at the end time, and return false since we cannot book the event. If we successfully iterate through the entire sorted dictionary without the sum exceeding 2, the event is successfully booked without causing a triple booking, so we return true.

Learn more about Segment Tree and Binary Search patterns.

Solution Approach

The solution uses a class MyCalendarTwo that maintains a SortedDict from the sortedcontainers module. This dictionary will keep track of how many events are starting or ending at any given time. This approach is akin to employing a sweep line algorithm commonly used in computational geometry. The key idea is to "sweep" across the calendar and keep a count of concurrent events.

When booking a new event, we apply these steps in the book method:

1. Increment the counter for the event's start time: self.sd[start] = self.sd.get(start, 0) + 1. This represents the beginning of an event.

2. Decrement the counter for the event's end time: self.sd[end] = self.sd.get(end, 0) - 1. This signals the end of an event.

After updating the counters, we need to check for triple bookings:

3. Iterate over all values in our sorted dictionary using self.sd.values(). We keep a running sum s that represents the current number of overlapping events.

   a. For each value v in the SortedDict, we add it to our running sum s += v.

   b. If at any point our sum exceeds 2 (if s > 2), it signifies that the attempted booking would result in a triple booking, thus we revert the changes done in step 1 and 2 by decrementing the start time counter and incrementing the end time counter:

   1self.sd[start] -= 1
   2self.sd[end] += 1

   c. Since adding the event leads to a triple booking, we return False.

4. If we complete the iteration without our running sum ever exceeding 2, it means we have successfully added the event without causing a triple booking, and we return True.

The SortedDict data structure allows efficient insertion, deletion, and iteration, which is crucial for the performance of this algorithm. By incrementing start times and decrementing end times, we smartly keep track of ongoing events, and by checking the running sum, we enforce the no-triple-booking rule.

Example Walkthrough

Let's go through an example to illustrate the solution approach using the MyCalendarTwo class.

First, we initialize the MyCalendarTwo object:

1my_calendar = MyCalendarTwo()

Our SortedDict starts empty as no events have been booked yet.

Now, let's try booking our first event [10, 20):

1result = my_calendar.book(10, 20)

• self.sd[10] becomes 1 because one event starts at time 10.
• self.sd[20] becomes -1 because one event ends at time 20.
• We iterate through the SortedDict, and the running sum s never exceeds 2, because we only have one event.
• The result is True, and the first event is successfully booked.

Now, suppose we book a second event [15, 25):

1result = my_calendar.book(15, 25)

• self.sd[15] gets incremented to 1, and since there is already one event overlapping at this time, the running total of events is now 2 at time 15 (as earlier, the running sum was 1 at 10, and then it becomes 2 at 15).
• self.sd[25] becomes -1.
• We iterate through the SortedDict, which now looks like this: 10: 1, 15: 1, 20: -1, 25: -1, and the running sum s never exceeds 2.
• The result is True, and the second event is successfully booked.

Finally, let's try booking a third event [20, 30):

1result = my_calendar.book(20, 30)

• self.sd[20] remains unchanged because when an event ends, another begins at the same time.
• self.sd[30] becomes -1.
• The sorted dictionary now is 10: 1, 15: 1, 20: -1, 25: -1, 30: -1, and while iterating, the running sum s does not exceed 2.
• The booking is successful as the sum s remains at most 2 at all points in time.

If we then attempt to book a fourth event [10, 15):

1result = my_calendar.book(10, 15)

• self.sd[10] would be incremented, going from 1 to 2, as there is now a second event starting at time 10.
• self.sd[15] would be decremented, going from 1 to 0.
• During iteration, when we reach time 15, the running sum s would become 3 (1 for the first event starting at 10, and 2 for the second and fourth events overlapping between 10 and 15) which exceeds our limit of 2.
• This would result in a triple booking, so we revert the changes (self.sd[10] goes back to 1 and self.sd[15] back to 1), and the result is False.

The event [10, 15) cannot be booked without causing a triple booking, and therefore, our MyCalendarTwo correctly returns False.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the book() method is primarily dictated by three operations:

1. Insertions into SortedDict: Inserting a start or end key involves maintaining the sorted order, which runs in O(log N) time for each insertion, where N is the number of unique timestamps in SortedDict.

2. Value updates: Each call to self.sd.get() is O(1) since it's a simple dictionary operation, but the subsequent update back into the SortedDict is O(1) because we're not changing the keys, only the values.

3. Iterating over the values and checking for overlapping events: This operation has a time complexity of O(N) because we are iterating through each timestamp's value once.

The worst-case complexity is dominated by the third step if N is the number of unique events (i.e., not the total number of calls to book()). Therefore, the worst-case time complexity per book() call is O(N).

Space Complexity

The space complexity is O(N) due to the storage requirements of the SortedDict, where N is the number of unique timestamps. The space required increases with each unique start or end timestamp that we add to the dict. There is no additional space usage that grows with the size of the input beyond what is used for the SortedDict.

Learn more about how to find time and space complexity quickly using problem constraints.