My Calendar I: Interval Overlap Detection

LeetCode 729, My Calendar I, is a design problem that tests whether you can efficiently detect interval overlaps. It shows up in scheduling systems, resource allocation, and anywhere you need to prevent double-booking. The core question is simple: given a growing list of booked time slots, can you quickly determine whether a new event conflicts with any existing one?

The problem

You need to implement a MyCalendar class with a single method, book(start, end). Each call represents a new event spanning the half-open interval [start, end). If the new event does not overlap with any previously booked event, add it to the calendar and return true. If it overlaps with any existing event, reject it and return false.

Two events overlap when one starts before the other ends and vice versa. Formally, events [s1, e1) and [s2, e2) overlap when s1 < e2 and s2 < e1. Notice the strict inequality: [10, 20) and [20, 30) do not overlap because 20 is not less than 20.

The calendar starts empty. Each book call either adds the event (no conflict) or rejects it (conflict with at least one existing booking).

The brute force approach

The most direct solution is to store all booked intervals in a list and check the new event against every existing one. For each book(start, end) call, iterate through all booked intervals and check for overlap using the condition start < booked_end and booked_start < end. If no overlap is found, append the new interval.

class MyCalendar:
    def __init__(self):
        self.bookings = []

    def book(self, start, end):
        for s, e in self.bookings:
            if start < e and s < end:
                return False
        self.bookings.append((start, end))
        return True

This works, but each book call scans all existing bookings, giving O(n) time per call. After n bookings, the total work is O(n^2). For large inputs, you can do better.

The key insight

If you keep the bookings sorted by start time, you can use binary search to find the right position for the new interval and only check its immediate neighbors for overlap. Python's bisect module makes this clean.

The idea: use bisect.insort to maintain a sorted list. Before inserting, use bisect_left to find where the new interval would go. Then check only the interval immediately before it (if any) and the interval at the insertion position (if any). If neither overlaps, insert the new interval.

Why does this work? In a sorted list, the only intervals that could overlap with [start, end) are the ones immediately adjacent in sorted order. An interval far to the left ends before start, and an interval far to the right starts after end.

from bisect import bisect_left, insort

class MyCalendar:
    def __init__(self):
        self.bookings = []

    def book(self, start, end):
        i = bisect_left(self.bookings, (start, end))

        if i > 0 and self.bookings[i - 1][1] > start:
            return False
        if i < len(self.bookings) and self.bookings[i][0] < end:
            return False

        insort(self.bookings, (start, end))
        return True

The bisect_left call finds the index where (start, end) would be inserted to keep the list sorted. The two checks after that are the overlap conditions for the left and right neighbors. If both pass, the new interval fits cleanly.

Step-by-step walkthrough

Let's trace through three calls: book(10, 20), book(15, 25), and book(20, 30).

The critical moment is the second call. When you try to book [15, 25), binary search tells you it would go at index 0 (since (15, 25) sorts after (10, 20) ... actually bisect_left on tuples compares the first element, and 15 > 10, so i = 1). Then you check the left neighbor at index 0: does bookings[0][1] > start? That is 20 > 15, which is true. Overlap detected, return false.

The third call, book(20, 30), lands at index 1. Check left neighbor at index 0: bookings[0][1] > start means 20 > 20, which is false. No left overlap. There is no right neighbor. So the booking succeeds.

Complexity analysis

The sorted list approach improves the overlap check from O(n) to O(log n), but the insertion into a list still costs O(n) in the worst case because elements need to shift. For the purposes of this problem, that is usually fast enough. If you need O(log n) for both search and insert, a balanced BST or an order-statistic tree would be the next step, but Python's bisect solution is clean and passes on LeetCode.

The building blocks

My Calendar I is built from two reusable patterns.

Interval overlap detection

The overlap condition s1 < e2 and s2 < e1 is the fundamental test for whether two half-open intervals intersect. You will see this exact check in Merge Intervals, Insert Interval, Meeting Rooms, and many other interval problems. Getting comfortable with when to use strict vs. non-strict inequality (depending on whether intervals are open or closed) is worth the practice.

Sorted order with binary search

Maintaining a sorted structure and using binary search to find neighbors is a general technique. Instead of scanning all elements, you narrow down to the one or two elements that could actually cause a conflict. This shows up in problems like:

• Insert Interval (find the insertion point, then merge neighbors)
• Meeting Rooms II (sort events, then sweep with a heap)
• Search Insert Position (pure binary search to find where an element belongs)

The pattern is always the same: sort to create an invariant, then exploit that invariant to skip unnecessary comparisons.

Edge cases

First booking. When the calendar is empty, any interval is accepted. The code handles this naturally since bisect_left returns 0 and both neighbor checks are skipped.

Adjacent intervals. [10, 20) and [20, 30) should not overlap. The half-open interval convention means 20 is not included in the first event. The strict inequality bookings[i-1][1] > start correctly allows this: 20 > 20 is false.

Contained interval. If you try to book [12, 15) when [10, 20) already exists, the left neighbor check catches it: 20 > 12 is true.

Large interval covering multiple bookings. If you try to book [5, 30) when [10, 20) exists, the right neighbor check catches it: 10 < 30 is true.

From understanding to recall

You have seen how to detect interval overlaps and why a sorted list with binary search improves performance. The overlap condition s1 < e2 and s2 < e1 is compact, but the direction of the inequalities is easy to mix up under pressure. Is it strict or non-strict? Do you compare starts with ends or starts with starts?

These details matter. Reading through the solution once gives you the concept, but reproducing it from scratch requires you to have internalized which neighbor to check and what inequality to use. Spaced repetition turns "I've seen this" into "I can write this cold."

Related posts

• Merge Intervals - The foundational interval merging pattern with sort-and-sweep
• Insert Interval - Insert into a sorted interval list and merge overlaps in one pass
• Meeting Rooms II - Count maximum simultaneous overlapping intervals with a heap