My Calendar I

How it works

By keeping events sorted by start time, we can use binary search to quickly find where a new event would be inserted. We only need to check the immediate neighbors (the event just before and just after the insertion point) for potential overlaps. If the previous event ends after our start time, or the next event starts before our end time, we have a conflict. This gives us logarithmic search time per booking.

Steps

1. Maintain a sorted collection of events ordered by start time.
2. When book(startTime, endTime) is called:
   • Use binary search to find the idx for the new event.
   • Check the event at the previous index (if it exists): if its end time is greater than startTime, return false.
   • Check the event at the current idx (if it exists): if its start time is less than endTime, return false.
3. If no conflicts, insert the new event at the correct position and return true.

Complexity

• Time complexity per book() function call:
  • O(log n) for Python's SortedList and the ordered-set implementations in Java and C++.
  • O(n) for the array/list-backed implementations (JavaScript, C#, Go, Kotlin, Swift, and Rust), since inserting at an arbitrary index can require shifting O(n) elements.
• Space complexity: O(n)

Things to watch for

Using Incorrect Overlap Condition

A common mistake is using <= instead of < when checking for overlaps. The correct overlap condition is startTime < end && start < endTime. Since intervals are half-open [start, end), an event ending exactly when another starts (e.g., [10, 20) and [20, 30)) does not constitute an overlap. Using <= would incorrectly reject valid adjacent bookings.

Forgetting to Handle Edge Cases for Empty Calendar

When implementing the BST or binary search approach, forgetting to handle the case when the calendar is empty can lead to null pointer exceptions or incorrect behavior. Always check if the root is null (BST) or if the events list is empty before performing searches or comparisons.

Off-by-One Errors in Binary Search Neighbor Checks

In the binary search with ordered set approach, a subtle bug occurs when checking neighbors at the insertion point. You must verify that idx - 1 exists before accessing the previous event, and that idx is within bounds before accessing the next event. Failing to perform these boundary checks results in index out of bounds errors for edge cases like inserting at the beginning or end of the sorted list.

class MyCalendar:

    def __init__(self):
        self.events = SortedList()

    def book(self, startTime: int, endTime: int) -> bool:
        idx = self.events.bisect_left((startTime, endTime))
        if idx > 0 and self.events[idx - 1][1] > startTime:
            return False
        if idx < len(self.events) and self.events[idx][0] < endTime:
            return False
        self.events.add((startTime, endTime))
        return True

class MyCalendar {
private:
    set<pair<int, int>> events;

public:
    MyCalendar() {}

    bool book(int startTime, int endTime) {
        if (startTime >= endTime) {
            return false;
        }

        auto next = events.lower_bound({startTime, startTime});
        if (next != events.end() && next->first < endTime) {
            return false;
        }
        if (next != events.begin()) {
            auto prev = std::prev(next);
            if (prev->second > startTime) {
                return false;
            }
        }

        events.insert({startTime, endTime});
        return true;
    }
};