731. My Calendar II

class MyCalendarTwo:
    """tc O(N^2) sc O(N)  N: number of event 
    main idea:record historical intevals  -> to get first overlaps added to overlaps record;  compare if target inteval exist an overlap in overlaps inteval    
    to check if inteval A overlaps inteval B  -> A_start < B_end  and   A_end  > B_start;  to get overlapped inteval, (max(A_start, B_start), min(A_end,B_end))
    1. chekc if target inteval has overlaps with overlaped inteval(occur twice) if yes -> return False can't be booked; 
    2. otherwise, check with historical intevals(appeared once) 
    3. find overlaps to save onto overlaped record) 
    """
    def __init__(self):
        self.one = []
        self.two = []

    def book(self, start: int, end: int) -> bool:
        for s,e in self.two:
            if start < e and end > s:
                return False 
        for s,e in self.one:
            overlap_s, overlap_e = max(s,start), min(e, end)
            if overlap_s < overlap_e:
                self.two.append((overlap_s , overlap_e))
        self.one.append((start,end))
        return True 

from sortedcontainers import SortedDict
class MyCalendarTwo:
    """
    main idea: count boundary changes 
    tc O(N^2) sc O(N)  N: number of event 
    """
    def __init__(self):
        self.d = SortedDict()       

    def book(self, start: int, end: int) -> bool:
        if start not in self.d: 
            self.d[start] = 0
        if end not in self.d:
            self.d[end] = 0
        self.d[start] += 1
        self.d[end] -= 1
        cnt = 0 
        for t in self.d:
            cnt += self.d[t]
            if cnt == 3:
                self.d[start] -= 1
                self.d[end] += 1 
                return False 
        return True