My Calendar II - Solution
Solutions and explanations
class MyCalendarTwo:
def __init__(self):
self.calendar = [] # Stores all booked events
self.overlaps = [] # Stores overlapping portions of booked events (double-booking portions)
def book(self, event_start: int, event_end: int) -> bool:
# If new event overlaps with the existing overlapping portions, then don't book
for start, end in self.overlaps:
if max(event_start, start) < min(event_end, end):
return False
# If there are any overlaps with the existing booked events, then add the overlapping portions to the overlaps list
for start, end in self.calendar:
intersect_start, intersect_end = max(event_start, start), min(event_end, end)
if intersect_start < intersect_end:
self.overlaps.append((intersect_start, intersect_end))
self.calendar.append((event_start, event_end)) # Accept the booking
return True
# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(event_start,event_end)
Complexity Analysis
Here, n is the number of booked calendar events.
Initialization:
- Time Complexity:
O(1) - Space Complexity:
O(1)- constant space is used initially.
Booking Operation
- Time Complexity:
O(n)per book() operation.- Scanning double-booked overlap segments:
O(n)to check if the new interval causes a triple booking. - Scanning single-booked intervals:
O(n)to identify new overlaps (only executed if no triple booking is found). - Overall per booking:
O(n)
- Scanning double-booked overlap segments:
- Space Complexity:
O(n)- In the worst case, each successful booking is added to the primary bookings list. A single booking may generate multiple new double-booked overlap segments, but across all bookings, the total number of such segments remains linear. (As the algorithm only tracks up to two layers of overlap, and never allows triple bookings)
Overall Space Compelxity: O(n) - Each booking is stored once, and although a single booking may create multiple overlapping segments,
but the total number of stored double-booked overlap segments remains linear because triple bookings are never allowed.
from sortedcontainers import SortedDict
class MyCalendarTwo:
def __init__(self):
self.bookings = SortedDict() # Store the changes at each point in time on a sorted timeline
def book(self, start: int, end: int) -> bool:
# Tentatively add the new event
self.bookings[start] = self.bookings.get(start, 0) + 1
self.bookings[end] = self.bookings.get(end, 0) - 1
running_count = 0
for change in self.bookings.values():
running_count += change
if running_count > 2: # Triple booking detected
# Rollback tentative changes
self.bookings[start] = self.bookings.get(start, 0) - 1
self.bookings[end] = self.bookings.get(end, 0) + 1
# Clean up zero-delta entries for both boundaries
if self.bookings[start] == 0:
self.bookings.pop(start)
if self.bookings[end] == 0:
self.bookings.pop(end)
return False
return True
# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(start,end)
Complexity Analysis
Here, n is the number of booking operations performed.
Initialization:
- Time Complexity:
O(1) - Space Complexity:
O(1)- constant space is used initially.
Booking Operation
- Time Complexity:
O(n)per book() operation.- Inserting/updating start and end events into Sorted Dictionary or Tree Map:
O(log n) - Iterating/sweeping through all event boundary points to compute running count (prefix sum) of active bookings:
O(n) - Overall per booking:
O(n)
- Inserting/updating start and end events into Sorted Dictionary or Tree Map:
- Space Complexity:
O(1)- Only constant extra variables used per operation.
Overall Space Compelxity: O(n) - Stores up to 2n event boundary points (start and end points) in the sorted hashmap, across all calls.