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.

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:

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

  2. 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.

💪
Level Up Your
Algo Skills

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.

Python Solution

1from sortedcontainers import SortedDict
2
3class MyCalendarTwo:
4    def __init__(self):
5        # Initialize a SortedDict to keep track of the booking times.
6        # Keys are the start or end of an event, and values are the net number
7        # of events starting or ending at that time.
8        self.booking_counts = SortedDict()
9
10    def book(self, start: int, end: int) -> bool:
11        # Increment the count for the start time of the new event.
12        self.booking_counts[start] = self.booking_counts.get(start, 0) + 1
13        # Decrement the count for the end time of the new event.
14        self.booking_counts[end] = self.booking_counts.get(end, 0) - 1
15
16        # Initialize a running sum to track number of simultaneous events.
17        running_sum = 0
18
19        # Iterate over all booked time points (both start and end times).
20        for count in self.booking_counts.values():
21            # Update the running sum which represents the count of current
22            # overlapping events at current time.
23            running_sum += count
24
25            # If there are more than 2 simultaneous events, it's a conflict.
26            if running_sum > 2:
27                # The booking is invalid, so we revert the increment and decrement
28                # for the start and end time of the new event.
29                self.booking_counts[start] -= 1
30                self.booking_counts[end] += 1
31
32                # Return False indicating booking was unsuccessful.
33                return False
34
35        # If no conflicts were found, return True indicating successful booking.
36        return True
37
38# Example usage of the MyCalendarTwo class:
39# calendar = MyCalendarTwo()
40# if calendar.book(10, 20):
41#     print("Booking from 10 to 20 is successful.")
42# else:
43#     print("Booking from 10 to 20 is unsuccessful.")
44

Java Solution

1import java.util.Map;
2import java.util.TreeMap;
3
4public class MyCalendarTwo {
5  
6    // Use TreeMap to automatically keep the keys sorted
7    private Map<Integer, Integer> timeMap = new TreeMap<>();
8
9    // Default constructor (not explicitly needed unless more constructors are provided)
10    public MyCalendarTwo() {
11    }
12
13    // Function to book a new event from start to end time
14    public boolean book(int start, int end) {
15        // Increase the counter at the start time
16        timeMap.put(start, timeMap.getOrDefault(start, 0) + 1);
17
18        // Decrease the counter at the end time
19        timeMap.put(end, timeMap.getOrDefault(end, 0) - 1);
20
21        int activeEvents = 0; // This will track the number of ongoing events
22
23        // Iterate through the values in TreeMap
24        for (int eventsCount : timeMap.values()) {
25            // Increment the count of active events
26            activeEvents += eventsCount;
27
28            // If at any point there are more than 2 active events, this booking overlaps with two other events
29            if (activeEvents > 2) {
30                // The booking is not possible, so revert the changes
31                timeMap.put(start, timeMap.get(start) - 1);
32                timeMap.put(end, timeMap.get(end) + 1);
33
34                // Return false as the booking overlaps and cannot be accepted
35                return false;
36            }
37        }
38        // The booking does not overlap with two or more events, so return true
39        return true;
40    }
41}
42

C++ Solution

1#include <map>
2using namespace std;
3
4class MyCalendarTwo {
5private:
6    // Map to keep track of the number of bookings at any given point in time.
7    map<int, int> bookings;
8
9public:
10    // Default constructor for MyCalendarTwo.
11    MyCalendarTwo() {
12        // The map is initially empty because no bookings have been made yet.
13    }
14
15    // Function to book a new event if it does not cause a triple booking.
16    bool book(int start, int end) {
17        // Increment the count for the start time.
18        bookings[start]++;
19
20        // Decrement the count for the end time.
21        bookings[end]--;
22
23        int count = 0; // To keep track of ongoing bookings.
24        // Iterate over the map to check if there is any point in time
25        // with more than two simultaneous bookings.
26        for(auto& [time, bookingCount] : bookings) {
27            count += bookingCount;
28            // If there are more than two bookings at a certain time,
29            // this means the current booking causes a triple booking.
30            if (count > 2) {
31                // Undo the changes - this booking is not allowed.
32                bookings[start]--;
33                bookings[end]++;
34
35                // Return false as the booking cannot be made without causing a triple booking.
36                return false;
37            }
38        }
39        // If the loop completes without finding a triple booking,
40        // the event can be successfully booked.
41        return true;
42    }
43};
44
45/**
46 * The class definition and methods should not be changed as per the requirements.
47 */
48
49// Usage example:
50// MyCalendarTwo* calendar = new MyCalendarTwo();
51// bool canBook = calendar->book(10, 20); // Returns true if the booking is successful.
52

Typescript Solution

1// Represents the booking counters at various timestamps.
2const bookings: { [key: number]: number } = {};
3
4// Function used to book a new event if it does not cause a triple booking.
5function book(start: number, end: number): boolean {
6    // If the booking key doesn't exist, initialize to zero prior to incrementing.
7    if (!bookings.hasOwnProperty(start)) bookings[start] = 0;
8    if (!bookings.hasOwnProperty(end)) bookings[end] = 0;
9
10    // Increment the count for the start time and decrement for the end time.
11    bookings[start]++;
12    bookings[end]--;
13
14    let count = 0; // To keep track of the current number of overlapping bookings.
15
16    // Sort the keys of the map since iteration order is not guaranteed in JavaScript/TypeScript.
17    const sortedKeys = Object.keys(bookings).map(key => parseInt(key)).sort((a, b) => a - b);
18
19    // Iterate over the sorted keys to check for triple bookings.
20    for (const time of sortedKeys) {
21        count += bookings[time];
22        // If there are more than two bookings at any time, it's a triple booking.
23        if (count > 2) {
24            // Undo the increment/decrement operations, as the booking cannot be finalized.
25            bookings[start]--;
26            bookings[end]++;
27
28            // Return false as the booking would lead to a triple booking.
29            return false;
30        }
31    }
32
33    // If there's no triple booking, the event can be booked.
34    return true;
35}
36
37/*
38 * Usage example:
39 * let canBook = book(10, 20); // Returns true if the booking is successful without causing a triple booking.
40 */
41

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.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫