0729-my-calendar-i.py

# Segment Tree solution

class MyCalendar:

    def __init__(self):
        self.calendar = CalendarNode(-1, -1)

    def book(self, start: int, end: int) -> bool:

        def bookHelper(cur, targetStart, targetEnd):
            if targetStart > cur.end:
                # go to the right
                if not cur.right:
                    # we can insert event
                    cur.right = CalendarNode(targetStart, targetEnd)
                    return True
                return bookHelper(cur.right, targetStart, targetEnd)
            elif targetEnd < cur.start:
                # got to the left
                if not cur.left:
                    # we can insert event
                    cur.left = CalendarNode(targetStart, targetEnd)
                    return True
                return bookHelper(cur.left, targetStart, targetEnd)
            return False
        
        return bookHelper(self.calendar, start, end-1) # "end-1" because "end" bound is exclusive (see example 1) 
    



class CalendarNode:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.left = None
        self.right = None