My Calendar III - Solution
Solutions and explanations
from sortedcontainers import SortedDict
class MyCalendarThree:
def __init__(self):
self.bookings = SortedDict() # Store the booking count changes at each point in time on a sorted timeline
def book(self, start: int, end: int) -> int:
self.bookings[start] = self.bookings.get(start, 0) + 1
self.bookings[end] = self.bookings.get(end, 0) - 1
k = 0 # Max Concurrent
running_count = 0
for change in self.bookings.values():
running_count += change
k = max(k, running_count)
return k
# Your MyCalendarThree object will be instantiated and called as such:
# obj = MyCalendarThree()
# 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 Time Complexity: O(n²) - For across n booking operations, with O(n) time per operation gives O(n²).
Overall Space Complexity: O(n) - Stores up to 2n event boundary points (start and end points) in the sorted hashmap, across all calls.