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:
startandendintegers representing time intervals[start, end). - Outputs: Boolean (
Trueif booked successfully,Falseotherwise). - 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 timexwhere both exist. - Constraints: Up to 1000 calls (
N <= 1000). Coordinates up to .
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 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 takes . Total time for all operations becomes roughly .
- Feasibility: With , operations. This is well within typical time limits (usually allowing 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 were larger (), 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
- Initialization: Create an instance variable
self.bookingsinitialized as an empty list to store tuples of(start, end). - 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 <= cORd <= a). Conversely, an intersection exists ifmax(a, c) < min(b, d). - 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.
- Iterate through all existing bookings in
- Success Case: If the loop completes without finding an overlap:
- Append
(start, end)toself.bookings. - Return
True.
- Append
Complexity Analysis
- Time Complexity: in total for all calls combined (where 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: . However, maintaining order in Python lists requires shifting elements (), negating gains unless using specialized libraries not available here.
- Space Complexity: to store the list of successful bookings where 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
bookwill 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), checkingend > booked_startensures 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 (): Python handles large integers automatically without overflow issues common in fixed-width integer languages.