Solution Explanation: My Calendar I

This problem asks to design a calendar system that allows booking events, but prevents double bookings. A double booking occurs when two events overlap in time. The solution uses an ordered set (or a similar data structure like a sorted map) to efficiently check for overlaps and book events.

Approach: Using an Ordered Set (TreeMap in Java, SortedDict in Python, etc.)

The core idea is to maintain a sorted collection of booked events. Each event is represented by its endTime. The startTime is implicitly stored, and we exploit the sorted nature of the data structure for efficient overlap checking.

1. Data Structure: We utilize an ordered set (like TreeMap in Java, SortedDict in Python, or std::map in C++). This structure automatically keeps entries sorted by keys (endTime in this case).

2. book(startTime, endTime) Function:

   a. Binary Search (Implicit): The book function implicitly performs a binary search to locate the position where the new event's endTime should be inserted. Methods like bisect_right in Python's SortedDict or ceilingEntry in Java's TreeMap directly provide this functionality.

   b. Overlap Check: After finding the correct position, we check for overlaps. We examine the event immediately after the insertion position (if one exists). An overlap occurs if:

   • There's a next event (nextEvent), and
   • The nextEvent's startTime is less than the new event's endTime.

   c. Booking: If no overlap is detected, we insert the new event (using its endTime as the key and startTime as the value in the map) into the ordered set and return true. Otherwise, we return false.

Time and Space Complexity Analysis

• Time Complexity: The dominant operation is the insertion and search within the ordered set. Ordered sets provide logarithmic time complexity for these operations: O(log n), where n is the number of booked events. Therefore, the overall time complexity of the book function is O(log n).

• Space Complexity: The space used is proportional to the number of booked events stored in the ordered set. The space complexity is O(n).

Code Examples (Python and Java)

Python:

from sortedcontainers import SortedDict
 
class MyCalendar:
    def __init__(self):
        self.calendar = SortedDict()  # Sorted dictionary to store events
 
    def book(self, start: int, end: int) -> bool:
        idx = self.calendar.bisect_right(start) #Finds insertion point
        if idx < len(self.calendar) and self.calendar.values()[idx] < end:
            return False  # Overlap detected
        self.calendar[end] = start  # Book the event
        return True

Java:

import java.util.TreeMap;
 
class MyCalendar {
    private TreeMap<Integer, Integer> calendar;
 
    public MyCalendar() {
        calendar = new TreeMap<>();
    }
 
    public boolean book(int startTime, int endTime) {
        Map.Entry<Integer, Integer> entry = calendar.ceilingEntry(startTime + 1); //Finds next event
        if (entry != null && entry.getValue() < endTime) {
            return false; // Overlap
        }
        calendar.put(endTime, startTime); // Book the event
        return true;
    }
}

Other language examples (C++, Go, TypeScript, Rust, JavaScript) in the original response demonstrate the same core approach, adapted to their respective data structures and syntax. The underlying algorithm remains consistent across all implementations.