My Calendar III — Difference Array / Seg Tree
Sanjeev SharmaAdvertisement
Problem
Return the maximum k-booking (max simultaneous events) after each new booking.
Approach — Difference Array with SortedDict
Increment at start, decrement at end. Max prefix sum = answer.
Time: O(n log n) | Space: O(n)
Solutions
Python — Difference Array
from sortedcontainers import SortedDict
class MyCalendarThree:
def __init__(self):
self.diff=SortedDict()
def book(self, start: int, end: int) -> int:
self.diff[start]=self.diff.get(start,0)+1
self.diff[end]=self.diff.get(end,0)-1
running=ans=0
for v in self.diff.values():
running+=v; ans=max(ans,running)
return ans
Complexity
- Time: O(n log n) per booking | Space: O(n)
Advertisement
