731. My Calendar II - cocoder39/coco39_LC GitHub Wiki

Time complexity:

O(N) to use bisect.insort
O(N) to iterate events. Once active==3, we need O(log N) to search the target index and O(N) to remove it
Overall time complexity for each new event is T = 2*O(N) + O(N) + 2 * (O(log N) + O(N)) = O(N)
For total N events the time complexity is O(N^2)

Java treeMap can be more efficient for insertion and deletion from BST, but overall time complexity won't change since we still need to iterate the treeMap with O(N) time for each event

class MyCalendarTwo:

    def __init__(self):
        self.events = []
        
    def book(self, start: int, end: int) -> bool:
        bisect.insort(self.events, (start, 1))
        bisect.insort(self.events, (end, -1))
        
        active = 0
        for timestamp, delta in self.events:
            active += delta
            if active == 3:
                self.events.pop(bisect.bisect_left(self.events, (start, 1)))
                self.events.pop(bisect.bisect_left(self.events, (end, -1)))
                return False
        return True