729. My Calendar I - Explanation

Problem Link



1. Iteration

Intuition

Two events overlap if one starts before the other ends and vice versa. For each new booking request, we need to check whether it conflicts with any existing event. We can store all booked events in a list and iterate through them to detect overlaps. If no conflict is found, we add the new event to the list.

Algorithm

  1. Maintain a list of booked events, where each event is stored as a (start, end) pair.
  2. When book(startTime, endTime) is called:
    • Iterate through all existing events.
    • For each event (start, end), check if startTime < end and start < endTime. If both conditions are true, there is an overlap, so return false.
  3. If no overlap is found, append the new event to the list and return true.
class MyCalendar:

    def __init__(self):
        self.events = []

    def book(self, startTime: int, endTime: int) -> bool:
        for start, end in self.events:
            if startTime < end and start < endTime:
                return False

        self.events.append((startTime, endTime))
        return True

Time & Space Complexity

  • Time complexity: O(n)O(n) for each book()book() function call.
  • Space complexity: O(n)O(n)

2. Binary Search Tree

Intuition

We can organize events in a binary search tree where each node represents a booked interval. The tree is ordered by start times: intervals that end before a node's start time go to the left subtree, and intervals that start after a node's end time go to the right subtree. When inserting a new interval, we traverse the tree to find where it fits without overlapping any existing node. If it overlaps with a node during traversal, we reject it.

Algorithm

  1. Each tree node stores (start, end) and has left and right children.
  2. When book(startTime, endTime) is called:
    • If the tree is empty, create the root node with this interval and return true.
    • Otherwise, traverse from the root:
      • If endTime <= node.start, the new interval belongs in the left subtree.
      • If startTime >= node.end, the new interval belongs in the right subtree.
      • Otherwise, there is an overlap, so return false.
    • When reaching a null child pointer, insert the new node there and return true.
class TreeNode:
    def __init__(self, start: int, end: int):
        self.start = start
        self.end = end
        self.left = None
        self.right = None

class MyCalendar:

    def __init__(self):
        self.root = None

    def _insert(self, node: TreeNode, start: int, end: int) -> bool:
        if end <= node.start:
            if not node.left:
                node.left = TreeNode(start, end)
                return True
            return self._insert(node.left, start, end)
        elif start >= node.end:
            if not node.right:
                node.right = TreeNode(start, end)
                return True
            return self._insert(node.right, start, end)
        else:
            return False

    def book(self, startTime: int, endTime: int) -> bool:
        if not self.root:
            self.root = TreeNode(startTime, endTime)
            return True
        return self._insert(self.root, startTime, endTime)

Time & Space Complexity

  • Time complexity: O(log⁡n)O(\log n) in average case, O(n)O(n) in worst case for each book()book() function call.
  • Space complexity: O(n)O(n)

3. Binary Search + Ordered Set

Intuition

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.

Algorithm

  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.
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

Time & Space Complexity

  • Time complexity: O(log⁡n)O(\log n) for each book()book() function call.
  • Space complexity: O(n)O(n)

Common Pitfalls

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.