My Calendar I — Sorted Dict / Segment Tree

Problem

Implement a calendar that returns false if a new booking overlaps with existing bookings.

Approach — SortedList / BST

For each booking [start, end), find the previous and next events in sorted order. Check for overlap.

Time: O(log n) per booking (with balanced BST) | Space: O(n)

Solutions

Python — SortedDict

from sortedcontainers import SortedDict
class MyCalendar:
    def __init__(self):
        self.cal=SortedDict()
    def book(self, start: int, end: int) -> bool:
        idx=self.cal.bisect_left(start)
        # check next event
        if idx<len(self.cal) and self.cal.peekitem(idx)[0]<end: return False
        # check previous event
        if idx>0 and self.cal.peekitem(idx-1)[1]>start: return False
        self.cal[start]=end; return True

Python — Simple list O(n²) fallback

class MyCalendar:
    def __init__(self): self.events=[]
    def book(self, s, e):
        for a,b in self.events:
            if s<b and e>a: return False
        self.events.append((s,e)); return True

Complexity

SortedDict: O(log n) per booking | Naive: O(n) per booking