732. My Calendar III

"""
main idea: boundry count (dict + sort )
1. each event, store its start and end time, and mark change delta among whole timeline
2. iterate whole timeline, based on mark to udpate accumutive intersection cnt
3. compare with global max cnt 
"""
class MyCalendarThree:
       
    def __init__(self):
        self.timeline = defaultdict(int)
    # tc O(N*NlgN)  sc  O(N)
    def book(self, start: int, end: int) -> int:
        self.timeline[start] += 1
        self.timeline[end] -= 1
        max_v = cur = 0
        for t in sorted(self.timeline.keys()):
            cur += self.timeline[t]
            max_v = max(max_v,cur)
        return max_v

#########################using sorteddict 
from sortedcontainers import SortedDict
class MyCalendarThree:
    def __init__(self):
        self.sd = SortedDict()
    # tc O(N*NlgN)  sc  O(N)
    def book(self, start: int, end: int) -> int:
        self.sd[start] = self.sd[start] + 1 if start in self.sd else 1 
        self.sd[end] = self.sd[end] - 1 if end in self.sd else -1
        return max(accumulate(self.sd.values()))

from bisect import bisect_left,bisect_right,insort_left
from heapq import heappush, heappop
"""
1. draw line segments  and sort start points
2. use heap to deal with ends
3. sorted start and end point will get the answer 

"""
class MyCalendarThree:
 # tc O(NlgN)   sc O(N)
    def __init__(self):
        self.begins,self.ends = [],[]
        self.max = 0
    def book(self, start: int, end: int) -> int:
        i,j = bisect_left(self.ends,start),bisect_right(self.begins,end)   # lgN + N   
        insort_left(self.begins,start,i,j)
        insort_left(self.ends,end,i,j)
        hp = []
        # MlgM =>  M   diff(j,i) , worst case N , so O(NlgN)

        for t_idx in range(i,j+1):
            while hp and hp[0] <= self.begins[t_idx]:
                heappop(hp)
            heappush(hp,self.ends[t_idx])
            self.max = max(self.max,len(hp))
        return self.max