731. My Calendar II

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 start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.

Implement the MyCalendarTwo class:

• MyCalendarTwo() Initializes the calendar object.
• boolean book(int start, int end) 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.

Approach 01:

#include <vector>
#include <algorithm>

using namespace std;

class MyCalendarTwo {
public:
    // Function to book an event, ensuring no triple booking
    bool book(int newStart, int newEnd) {
        // Check for any overlap that would cause triple booking
        for (const auto& [overlapStart, overlapEnd] : overlapRanges) {
            if (max(newStart, overlapStart) < min(newEnd, overlapEnd))
                return false; // Triple booking found, return false
        }

        // Check existing events and add to overlaps if needed
        for (const auto& [existingStart, existingEnd] : bookedRanges) {
            int overlapStart = max(newStart, existingStart);
            int overlapEnd = min(newEnd, existingEnd);
            if (overlapStart < overlapEnd) {
                overlapRanges.emplace_back(overlapStart, overlapEnd);
            }
        }

        // Add the new booking to the list of booked ranges
        bookedRanges.emplace_back(newStart, newEnd);
        return true;
    }

private:
    // Vector to store all the booked events as pairs of start and end times
    vector<pair<int, int>> bookedRanges;

    // Vector to store overlapping ranges between events
    vector<pair<int, int>> overlapRanges;
};

class MyCalendarTwo:

    def __init__(self):
        # List to store all booked events
        self.bookedRanges = []
        
        # List to store ranges where overlaps occur
        self.overlapRanges = []

    # Function to book an event, ensuring no triple booking
    def book(self, newStart, newEnd):
        # Check for any overlap that would cause triple booking
        for overlapStart, overlapEnd in self.overlapRanges:
            if max(newStart, overlapStart) < min(newEnd, overlapEnd):
                return False  # Triple booking found, return False

        # Check existing bookings and add to overlaps if needed
        for existingStart, existingEnd in self.bookedRanges:
            overlapStart = max(newStart, existingStart)
            overlapEnd = min(newEnd, existingEnd)
            if overlapStart < overlapEnd:
                self.overlapRanges.append((overlapStart, overlapEnd))

        # Add the new booking to the list of booked ranges
        self.bookedRanges.append((newStart, newEnd))
        return True

Time Complexity

• Checking for Triple Booking:

  The algorithm iterates over the overlapRanges vector to check for potential triple bookings. In the worst case, the size of this vector grows linearly with the number of bookings, so checking all overlaps takes \(O(n)\), where \(n\) is the number of previous bookings.

• Checking for Overlapping Ranges:

  After checking for triple bookings, the algorithm iterates over the bookedRanges vector to find overlaps with the new event. This also takes \(O(n)\) time since it checks each previously booked event.

• Overall Time Complexity:

  Each call to the book() function performs two loops over the overlapRanges and bookedRanges vectors, leading to an overall time complexity of \(O(n)\) per call, where \(n\) is the number of events already booked.

Space Complexity

• Auxiliary Space:

  The space complexity is dominated by the storage of booked events and their overlaps. Both bookedRanges and overlapRanges grow linearly with the number of events. Thus, the space complexity for storing these ranges is \(O(n)\).

• Overall Space Complexity:

  The overall space complexity is \(O(n)\), where \(n\) is the number of bookings, as both the bookedRanges and overlapRanges vectors grow proportionally with the number of events.