729. My Calendar I

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 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 MyCalendar class:

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

Approach 01:

class MyCalendar {
public:
    // Function to book a new event if there are no conflicts with existing
    // events
    bool book(int newStart, int newEnd) {
        // Check for any overlap with already booked events
        for (const auto& [existingStart, existingEnd] : calendar) {
            if (max(newStart, existingStart) < min(newEnd, existingEnd)){
                return false; // Overlap found, booking is not possible
            }
        }
        // No conflicts, book the event
        calendar.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>> calendar;
};

class MyCalendar:
    def __init__(self):
        # Initialize an empty list to store the booked events
        self.bookedEvents = []

    # Function to book a new event if there are no conflicts with existing events
    def book(self, newStart, newEnd):
        # Check for any overlap with already booked events
        for existingStart, existingEnd in self.bookedEvents:
            if max(newStart, existingStart) < min(newEnd, existingEnd):
                return False  # Overlap found, booking is not possible
        
        # No conflicts, book the event
        self.bookedEvents.append((newStart, newEnd))
        return True

Time Complexity

• Loop Iteration:

  Each time a new event is booked, the algorithm checks for conflicts by iterating over all previously booked events in the calendar vector. Since there are \(n\) previously booked events, the time complexity for each booking attempt is \(O(n)\).

• Overall Time Complexity:

  If there are \(n\) events to be booked, and each booking takes \(O(n)\) time, the total time complexity after booking \(n\) events is \(O(n^2)\).

Space Complexity

• Auxiliary Space:

  The algorithm stores each booked event in the calendar vector. Since each event requires constant space, the space complexity for storing \(n\) events is \(O(n)\).

• Overall Space Complexity:

  The overall space complexity is \(O(n)\), where \(n\) is the number of booked events.