732. My Calendar III - cocoder39/coco39_LC GitHub Wiki

732. My Calendar III

For each new event, O(N) to insert and O(N) to iterate the list so T = O(N). For all N events, total time complexity is O(N^2). For Java, we can use TreeMap, which offers O(log N) time complexity for insertion into a BST. The overall time complexity won't change since we still need to iterate the entire TreeMap.

class MyCalendarThree:

    def __init__(self):
        self.events = []

    def book(self, start: int, end: int) -> int:
        bisect.insort(self.events, (start, 1)) 
        bisect.insort(self.events, (end, -1)) 
        
        active = 0
        res = 0
        for timestamp, delta in self.events:
            active += delta
            res = max(res, active)
        return res