Problem statement

https://leetcode.com/problems/my-calendar-i/

Solution

Let us keep sorted list with all 2n start and end points. For each new interval, perform binary search and check if it has intersections with others.

Complexity

Complexity of one book is O(log n), complexity of all algorithm is O(n log n).

Code

from sortedcontainers import SortedList

class MyCalendar:
    def __init__(self):
        self.arr = SortedList()
        
    def book(self, start, end):
        q1 = SortedList.bisect_right(self.arr, start)
        q2 = SortedList.bisect_left(self.arr, end)
        if q1 == q2 and q1 % 2 == 0:
            self.arr.add(start)
            self.arr.add(end)
            return True
        return False

Remark

See also similar problem 0253 Meeting Rooms II.