Domain 2MediumMEDIUM

My Calendar I

LeetCode problem 729: My Calendar I (medium).

Domain: medium•Updated: 2026-08-30
#Array

Problem Breakdown

We need to implement a calendar system that prevents double bookings. The core challenge is managing state across multiple method calls while enforcing the non-overlap rule efficiently within given constraints.

  • Inputs: start and end integers representing time intervals [start, end).
  • Outputs: Boolean (True if booked successfully, False otherwise).
  • State Management: The calendar persists between calls; we must store successful bookings to check against future requests.
  • Key Constraint Definition: A double booking occurs if there is a non-empty intersection of real numbers in the intervals [start1, end1) and [start2, end2). Crucially, this means touching endpoints (e.g., one ends at 20, another starts at 20) are allowed because they do not share any time x where both exist.
  • Constraints: Up to 1000 calls (N <= 1000). Coordinates up to 10910^9.

Intuition

The most straightforward way to ensure no overlaps is to check the new interval against every previously booked event before adding it.

Brute Force Analysis: If we simply store a list of all successful bookings, for each book call, we iterate through this list and verify if any existing booking conflicts with the new one.

  • Complexity: If KK is the total number of calls (up to 1000), in the worst case every previous event overlaps partially until rejected or accepted. Checking against a list of size ii takes O(i)O(i). Total time for all operations becomes roughly ∑i=1N−1i≈O(N2)\sum_{i=1}^{N-1} i \approx O(N^2).
  • Feasibility: With N=1000N = 1000, N2=1,000,000N^2 = 1,000,000 operations. This is well within typical time limits (usually allowing ∼108\sim 10^8 ops/sec). Therefore, a linear scan per call is acceptable here and demonstrates clear logic without unnecessary complexity for this specific constraint set.
  • Scalability Note: If NN were larger (>2×104> 2 \times 10^4), we would need to optimize using binary search (e.g., maintaining sorted intervals) or a Segment Tree, but Python’s standard library lacks built-in balanced BSTs like Java’s TreeSet, making the list approach pragmatic for this problem.

Approach

  1. Initialization: Create an instance variable self.bookings initialized as an empty list to store tuples of (start, end).
  2. Overlap Check Logic: Two intervals [a, b) and [c, d) overlap if they share any common time point. Mathematically, this happens unless one ends before or exactly when the other starts (b <= c OR d <= a). Conversely, an intersection exists if max(a, c) < min(b, d).
  3. Validation Loop: For every new booking request (start, end):
    • Iterate through all existing bookings in self.bookings.
    • If any existing booking overlaps with the current one (using the intersection logic), reject immediately and return False.
  4. Success Case: If the loop completes without finding an overlap:
    • Append (start, end) to self.bookings.
    • Return True.

Complexity Analysis

  • Time Complexity: O(N2)O(N^2) in total for all calls combined (where NN is max 1000). Each call performs a linear scan of existing bookings. Given the constraint, this fits comfortably within time limits.
    • If optimized with binary search on sorted intervals: O(Klog⁡N)O(K \log N). However, maintaining order in Python lists requires shifting elements (O(N)O(N)), negating gains unless using specialized libraries not available here.
  • Space Complexity: O(N)O(N) to store the list of successful bookings where NN is the number of accepted events (max 1000).

Solution

class MyCalendar:
    def __init__(self):
        self.bookings = []

    def book(self, start: int, end: int) -> bool:
        # Check for overlap with every existing booking.
        # Two intervals [s1, e1) and [s2, e2) do NOT overlap if s2 >= e1 OR s1 >= e2.
        # If they DO overlap (i.e., not disjoint), we reject the new event.
        
        for booked_start, booked_end in self.bookings:
            # Check intersection condition: max(starts) < min(ends) implies overlap
            if start < booked_end and end > booked_start:
                return False
        
        # If no overlaps found after checking all existing events
        self.bookings.append((start, end))
        return True

# Example usage (not part of class definition):
# cal = MyCalendar()
# print(cal.book(10, 20))   # true
# print(cal.book(15, 25))   # false
# print(cal.book(20, 30))   # true

Edge Cases Handled

  • Empty Calendar: The first call to book will find an empty list in the loop and successfully add the event.
  • Adjacent Intervals (e.g., [10, 20) then [20, 30)): Since intervals are half-open [start, end), checking end > booked_start ensures that if one ends exactly when another starts (booked_end == start), they do not overlap.
  • Nested Intervals: Logic correctly identifies containment (e.g., [15, 20) inside [10, 30)) as an intersection because max(15, 10)=15 < min(20, 30)=20.
  • Large Coordinates (10910^9): Python handles large integers automatically without overflow issues common in fixed-width integer languages.