• Posts

Problem 731 My Calendar II

Problem Statement

Link - Problem 731

Question

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 <= 109
• At most 1000 calls will be made to book.

Solution

class MyCalendarTwo {
public:
    map<int, int> bookingCount;
    int maxOverlappedBooking;

    MyCalendarTwo() { maxOverlappedBooking = 2; }

    bool book(int start, int end) {
        bookingCount[start]++;
        bookingCount[end]--;

        int overlappedBooking = 0;
        for (pair<int, int> bookings : bookingCount) {
            overlappedBooking += bookings.second;
            if (overlappedBooking > maxOverlappedBooking) {
                bookingCount[start]--;
                bookingCount[end]++;

                if (bookingCount[start] == 0) {
                    bookingCount.erase(start);
                }
                if (bookingCount[end] == 0) {
                    bookingCount.erase(end);
                }

                return false;
            }
        }

        return true;
    }
};

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo* obj = new MyCalendarTwo();
 * bool param_1 = obj->book(start,end);
 */

Complexity Analysis

| Algorithm            | Time Complexity | Space Complexity |
| -------------------- | --------------- | ---------------- |
| Sweep line algorithm | O(n)            | O(n)             |

Explanation

Intial Thoughts

To approach this problem, we need to think about how to efficiently track bookings and overlaps. We could use a data structure that allows us to store and update bookings easily, such as a map or an array. Key considerations include how to identify overlaps, how to handle edge cases like booking start and end times, and how to keep track of booking counts. Main points to consider are: identifying the right data structure, understanding how to calculate overlaps, determining how to handle edge cases, thinking about how to optimize the solution for performance, and considering how to implement the booking count logic.

Intuitive Analysis

Intuitively, we can solve this problem by visualizing the calendar as a series of lines representing bookings. When a new booking is added, we check for overlaps by looking for any existing bookings that share a common time slot. A key insight is to recognize that a triple booking occurs when three lines overlap at the same point. To intuitively solve this, we need to: consider using a sweep line approach to track overlaps, think about how to update the booking count as new bookings are added, recognize the importance of handling edge cases correctly, understand how to optimize the solution to avoid unnecessary checks, and think about how to use the data structure to efficiently track and update booking information.

1. Intuition

• To solve this problem, we need to track the number of overlapping bookings at any given time.
• We can use a map to store the count of bookings at each time point, where the key is the time and the value is the count.
• When a new booking is added, we increment the count at the start time and decrement the count at the end time.
• We then iterate through the map to check if there are any time points with more than two overlapping bookings.
• If we find such a time point, we cancel the new booking and return false.
• The key insight here is that we only need to check for overlapping bookings when a new booking is added, not when a booking is removed.
• This approach works because it ensures that we never have more than two overlapping bookings at any given time.

2. Implementation

• We initialize a map bookingCount to store the count of bookings at each time point, and a variable maxOverlappedBooking to store the maximum allowed overlapping bookings.
• In the book function, we increment the count at the start time and decrement the count at the end time using bookingCount[start]++ and bookingCount[end]--.
• We then iterate through the map using a for loop to check if there are any time points with more than two overlapping bookings.
• If we find such a time point, we cancel the new booking by decrementing the count at the start time and incrementing the count at the end time using bookingCount[start]-- and bookingCount[end]++.
• We also remove any time points with a count of zero from the map using bookingCount.erase(start) and bookingCount.erase(end).
• Finally, we return true if the new booking is successful, and false otherwise.
• The time complexity of this solution is O(n), where n is the number of bookings, and the space complexity is also O(n).

Complexity Analysis

Time Complexity:

• The time complexity for the book operation is O(n) because in the worst case, it iterates over all existing bookings stored in bookingCount to check for overlapping bookings.
• The dominant operation is the for loop that traverses bookingCount, where n represents the total number of start and end times stored.
• This justifies the Big O classification as O(n) since the number of steps grows linearly with the number of bookings.

Space Complexity:

• The space complexity of the MyCalendarTwo class is O(n) because it uses a map called bookingCount to store start and end times of bookings.
• The map data structure’s size can grow up to n in the worst case, where n is the total number of bookings added, thus affecting memory usage.
• This justifies the O(n) space complexity, as the amount of memory used grows linearly with the number of bookings stored in bookingCount.

Footnote

This question is rated as Medium difficulty.

Hints

Store two sorted lists of intervals: one list will be all times that are at least single booked, and another list will be all times that are definitely double booked. If none of the double bookings conflict, then the booking will succeed, and you should update your single and double bookings accordingly.

Similar Questions: