729. My Calendar I Solution & Explanation

The problem

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.

A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.).

The event can be represented as a pair of integers startTime and endTime that represents a booking on the half-open interval [startTime, endTime), the range of real numbers x such that startTime <= x < endTime.

Implement the MyCalendar class:

MyCalendar() Initializes the calendar object.
boolean book(int startTime, int endTime) Returns true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

Example 1:

Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]

Explanation
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.

Constraints:

0 <= start < end <= 10⁹
At most 1000 calls will be made to book.

Approach overview

Problem Overview: Design a calendar system that supports booking events represented as half‑open intervals [start, end). A booking should only succeed if the new event does not overlap with any existing event. The task is to efficiently detect interval conflicts while storing previously accepted bookings.

Approach 1: Brute Force with List (Time: O(n) per booking, Space: O(n))

Store all accepted bookings in a simple list of intervals. When a new booking request arrives, iterate through every stored interval and check for overlap. Two intervals overlap if start < existingEnd and end > existingStart. If any overlap is found, reject the booking; otherwise append the interval to the list. This approach relies only on basic array-style storage and linear scanning. It works well for small input sizes and is easy to implement during an interview, but performance degrades as the number of bookings grows because every operation scans the entire list.

Approach 2: Balanced Tree Using TreeMap (Time: O(log n) per booking, Space: O(n))

A more scalable solution keeps bookings sorted by start time using a balanced search tree such as TreeMap in Java or an ordered structure in C++/Python. Each key represents the start time and the value stores the end time. When inserting a new interval, you only need to check the immediate neighbors in sorted order. Use a floor search to find the previous interval and verify that its end does not exceed the new start. Then use a ceiling search to ensure the next interval does not begin before the new end. Because the structure maintains sorted order internally, each lookup and insertion runs in O(log n). This approach leverages concepts from binary search and ordered set data structures.

Some advanced implementations also model the calendar with a segment tree to support more complex booking queries, but for the constraints of My Calendar I that level of structure is unnecessary.

Recommended for interviews: The balanced tree approach is what most interviewers expect. It shows you understand ordered data structures and how to check only adjacent intervals instead of scanning the entire dataset. Starting with the brute force solution demonstrates correctness and reasoning, while optimizing to O(log n) using a tree structure demonstrates algorithmic maturity.

Approach 1: Approach 1: Brute Force with List

This approach uses a simple list to store existing bookings. For each new booking, we check against all previously booked intervals to ensure there is no overlap. If an overlap is found, the booking is denied; otherwise, it's added to the list. Although straightforward, this approach can be inefficient for many bookings, as each booking incurs a linear scan through the list of existing bookings.

Python

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

    def book(self, start: int, end: int) -> bool:
        for s, e in self.booked:
            if start < e and end > s:
                return False
        self.booked.append((start, end))
        return True


my_calendar = MyCalendar()
print(my_calendar.book(10, 20))  # True
print(my_calendar.book(15, 25))  # False
print(my_calendar.book(20, 30))  # True

Java

import java.util.ArrayList;
import java.util.List;

class MyCalendar {
    List<int[]> calendar;
    
    public MyCalendar() {
        calendar = new ArrayList<>();
    }
    
    public boolean book(int start, int end) {
        for (int[] event : calendar) {
            if (start < event[1] && end > event[0]) {
                return false;
            }
        }
        calendar.add(new int[]{start, end});
        return true;
    }

    public static void main(String[] args) {
        MyCalendar myCalendar = new MyCalendar();
        System.out.println(myCalendar.book(10, 20)); // True
        System.out.println(myCalendar.book(15, 25)); // False
        System.out.println(myCalendar.book(20, 30)); // True
    }
}

C++

#include <vector>
#include <iostream>

class MyCalendar {
public:
    MyCalendar() {}

    bool book(int start, int end) {
        for (const auto &event : events) {
            if (start < event.second && end > event.first) {
                return false;
            }
        }
        events.push_back({start, end});
        return true;
    }

private:
    std::vector<std::pair<int, int>> events;
};

int main() {
    MyCalendar myCalendar;
    std::cout << std::boolalpha << myCalendar.book(10, 20) << std::endl; // True
    std::cout << myCalendar.book(15, 25) << std::endl; // False
    std::cout << myCalendar.book(20, 30) << std::endl; // True
    return 0;
}

JavaScript

class MyCalendar {
  constructor() {
    this.booked = [];
  }

  book(start, end) {
    for (const [s, e] of this.booked) {
      if (start < e && end > s) {
        return false;
      }
    }
    this.booked.push([start, end]);
    return true;
  }
}

const myCalendar = new MyCalendar();
console.log(myCalendar.book(10, 20)); // True
console.log(myCalendar.book(15, 25)); // False
console.log(myCalendar.book(20, 30)); // True

#include <stdbool.h>
#include <stdio.h>

#define MAX_EVENTS 1000

int booked[MAX_EVENTS][2];
int count = 0;

bool book(int start, int end) {
    for (int i = 0; i < count; i++) {
        if (start < booked[i][1] && end > booked[i][0]) {
            return false;
        }
    }
    booked[count][0] = start;
    booked[count][1] = end;
    count++;
    return true;
}

int main() {
    printf("%d\n", book(10, 20)); // True
    printf("%d\n", book(15, 25)); // False
    printf("%d\n", book(20, 30)); // True
    return 0;
}

using System;
using System.Collections.Generic;

public class MyCalendar {
    private List<Tuple<int, int>> calendar;

    public MyCalendar() {
        calendar = new List<Tuple<int, int>>();
    }

    public bool Book(int start, int end) {
        foreach (var interval in calendar) {
            if (start < interval.Item2 && end > interval.Item1) {
                return false;
            }
        }
        calendar.Add(Tuple.Create(start, end));
        return true;
    }

    public static void Main() {
        MyCalendar myCalendar = new MyCalendar();
        Console.WriteLine(myCalendar.Book(10, 20)); // True
        Console.WriteLine(myCalendar.Book(15, 25)); // False
        Console.WriteLine(myCalendar.Book(20, 30)); // True
    }
}

Python handles bookings with a list of tuples. The 'book' method checks overlaps by iterating through existing bookings and only appends if no overlap is found.

Complexity

Time Complexity: O(N) per booking.
Space Complexity: O(N).

Try this approach in the editor

Approach 2: Approach 2: Balanced Tree Using TreeMap

This approach leverages a data structure like a TreeMap (Java) or SortedDict (Python) to efficiently manage and query intervals. These structures allow us to quickly find the nearest existing intervals to check for overlaps, enabling faster insert operations compared to a simple list. By maintaining the intervals in a sorted order, we can reduce the number of overlaps checks necessary for each new booking.

Python

from sortedcontainers import SortedDict

class MyCalendar:
    def __init__(self):
        self.calendar = SortedDict()

    def book(self, start: int, end: int) -> bool:
        if self.calendar:
            # predecessor: the largest key less than or equal to 'start'
            preds = self.calendar.bisect_right(start) - 1
            if preds != -1 and self.calendar.iloc[preds] > start:
                return False
            # successor: the smallest key greater than 'start'
            succs = self.calendar.bisect_left(start)
            if succs != len(self.calendar) and end > self.calendar.iloc[succs]:
                return False
        self.calendar[start] = end
        return True


my_calendar = MyCalendar()
print(my_calendar.book(10, 20))  # True
print(my_calendar.book(15, 25))  # False
print(my_calendar.book(20, 30))  # True

Java

import java.util.TreeMap;

class MyCalendar {
    private TreeMap<Integer, Integer> calendar;
    
    public MyCalendar() {
        calendar = new TreeMap<>();
    }

    public boolean book(int start, int end) {
        Integer prev = calendar.floorKey(start);
        Integer next = calendar.ceilingKey(start);
    
        if ((prev == null || calendar.get(prev) <= start) && (next == null || end <= next)) {
            calendar.put(start, end);
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        MyCalendar myCalendar = new MyCalendar();
        System.out.println(myCalendar.book(10, 20)); // True
        System.out.println(myCalendar.book(15, 25)); // False
        System.out.println(myCalendar.book(20, 30)); // True
    }
}

C++

#include <map>
#include <iostream>

class MyCalendar {
public:
    MyCalendar() {}

    bool book(int start, int end) {
        auto next = calendar.lower_bound(start);
        if (next != calendar.end() && next->first < end) {
            return false;
        }
        if (next != calendar.begin()) {
            auto prev = std::prev(next);
            if (prev->second > start) {
                return false;
            }
        }
        calendar[start] = end;
        return true;
    }

private:
    std::map<int, int> calendar;
};

int main() {
    MyCalendar myCalendar;
    std::cout << myCalendar.book(10, 20) << std::endl; // True
    std::cout << myCalendar.book(15, 25) << std::endl; // False
    std::cout << myCalendar.book(20, 30) << std::endl; // True
    return 0;
}

The Python solution uses 'SortedDict' from the 'sortedcontainers' module for efficient sorting and searching. It checks adjacent intervals using 'bisect_right' and 'bisect_left', minimizing overlap checks.

Complexity

Time Complexity: O(log N) per booking using SortedDict.
Space Complexity: O(N).

Try this approach in the editor

Approach 3: Ordered Set

We can use an ordered set to store the schedule. An ordered set can perform insert, delete, and search operations in O(log n) time. The elements in the ordered set are sorted by the endTime of the schedule in ascending order.

When calling the book(start, end) method, we search for the first schedule in the ordered set with an end time greater than start. If it exists and its start time is less than end, it means there is a double booking, and we return false. Otherwise, we insert end as the key and start as the value into the ordered set and return true.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the number of schedules.

TypeScript

class MyCalendar {
    tm: TreeMap<number, number>;
    constructor() {
        this.tm = new TreeMap<number, number>();
    }

    book(startTime: number, endTime: number): boolean {
        const e = this.tm.higher(startTime);
        if (e && e[1] < endTime) {
            return false;
        }
        this.tm.set(endTime, startTime);
        return true;
    }
}

type Compare<T> = (lhs: T, rhs: T) => number;

class RBTreeNode<T = number> {
    data: T;
    count: number;
    left: RBTreeNode<T> | null;
    right: RBTreeNode<T> | null;
    parent: RBTreeNode<T> | null;
    color: number;
    constructor(data: T) {
        this.data = data;
        this.left = this.right = this.parent = null;
        this.color = 0;
        this.count = 1;
    }

    sibling(): RBTreeNode<T> | null {
        if (!this.parent) return null; // sibling null if no parent
        return this.isOnLeft() ? this.parent.right : this.parent.left;
    }

    isOnLeft(): boolean {
        return this === this.parent!.left;
    }

    hasRedChild(): boolean {
        return (
            Boolean(this.left && this.left.color === 0) ||
            Boolean(this.right && this.right.color === 0)
        );
    }
}

class RBTree<T> {
    root: RBTreeNode<T> | null;
    lt: (l: T, r: T) => boolean;
    constructor(compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0)) {
        this.root = null;
        this.lt = (l: T, r: T) => compare(l, r) < 0;
    }

    rotateLeft(pt: RBTreeNode<T>): void {
        const right = pt.right!;
        pt.right = right.left;

        if (pt.right) pt.right.parent = pt;
        right.parent = pt.parent;

        if (!pt.parent) this.root = right;
        else if (pt === pt.parent.left) pt.parent.left = right;
        else pt.parent.right = right;

        right.left = pt;
        pt.parent = right;
    }

    rotateRight(pt: RBTreeNode<T>): void {
        const left = pt.left!;
        pt.left = left.right;

        if (pt.left) pt.left.parent = pt;
        left.parent = pt.parent;

        if (!pt.parent) this.root = left;
        else if (pt === pt.parent.left) pt.parent.left = left;
        else pt.parent.right = left;

        left.right = pt;
        pt.parent = left;
    }

    swapColor(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
        const tmp = p1.color;
        p1.color = p2.color;
        p2.color = tmp;
    }

    swapData(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
        const tmp = p1.data;
        p1.data = p2.data;
        p2.data = tmp;
    }

    fixAfterInsert(pt: RBTreeNode<T>): void {
        let parent = null;
        let grandParent = null;

        while (pt !== this.root && pt.color !== 1 && pt.parent?.color === 0) {
            parent = pt.parent;
            grandParent = pt.parent.parent;

            /*  Case : A
                Parent of pt is left child of Grand-parent of pt */
            if (parent === grandParent?.left) {
                const uncle = grandParent.right;

                /* Case : 1
                   The uncle of pt is also red
                   Only Recoloring required */
                if (uncle && uncle.color === 0) {
                    grandParent.color = 0;
                    parent.color = 1;
                    uncle.color = 1;
                    pt = grandParent;
                } else {
                    /* Case : 2
                       pt is right child of its parent
                       Left-rotation required */
                    if (pt === parent.right) {
                        this.rotateLeft(parent);
                        pt = parent;
                        parent = pt.parent;
                    }

                    /* Case : 3
                       pt is left child of its parent
                       Right-rotation required */
                    this.rotateRight(grandParent);
                    this.swapColor(parent!, grandParent);
                    pt = parent!;
                }
            } else {
                /* Case : B
               Parent of pt is right child of Grand-parent of pt */
                const uncle = grandParent!.left;

                /*  Case : 1
                    The uncle of pt is also red
                    Only Recoloring required */
                if (uncle != null && uncle.color === 0) {
                    grandParent!.color = 0;
                    parent.color = 1;
                    uncle.color = 1;
                    pt = grandParent!;
                } else {
                    /* Case : 2
                       pt is left child of its parent
                       Right-rotation required */
                    if (pt === parent.left) {
                        this.rotateRight(parent);
                        pt = parent;
                        parent = pt.parent;
                    }

                    /* Case : 3
                       pt is right child of its parent
                       Left-rotation required */
                    this.rotateLeft(grandParent!);
                    this.swapColor(parent!, grandParent!);
                    pt = parent!;
                }
            }
        }
        this.root!.color = 1;
    }

    delete(val: T): boolean {
        const node = this.find(val);
        if (!node) return false;
        node.count--;
        if (!node.count) this.deleteNode(node);
        return true;
    }

    deleteAll(val: T): boolean {
        const node = this.find(val);
        if (!node) return false;
        this.deleteNode(node);
        return true;
    }

    deleteNode(v: RBTreeNode<T>): void {
        const u = BSTreplace(v);

        // True when u and v are both black
        const uvBlack = (u === null || u.color === 1) && v.color === 1;
        const parent = v.parent!;

        if (!u) {
            // u is null therefore v is leaf
            if (v === this.root) this.root = null;
            // v is root, making root null
            else {
                if (uvBlack) {
                    // u and v both black
                    // v is leaf, fix double black at v
                    this.fixDoubleBlack(v);
                } else {
                    // u or v is red
                    if (v.sibling()) {
                        // sibling is not null, make it red"
                        v.sibling()!.color = 0;
                    }
                }
                // delete v from the tree
                if (v.isOnLeft()) parent.left = null;
                else parent.right = null;
            }
            return;
        }

        if (!v.left || !v.right) {
            // v has 1 child
            if (v === this.root) {
                // v is root, assign the value of u to v, and delete u
                v.data = u.data;
                v.left = v.right = null;
            } else {
                // Detach v from tree and move u up
                if (v.isOnLeft()) parent.left = u;
                else parent.right = u;
                u.parent = parent;
                if (uvBlack) this.fixDoubleBlack(u);
                // u and v both black, fix double black at u
                else u.color = 1; // u or v red, color u black
            }
            return;
        }

        // v has 2 children, swap data with successor and recurse
        this.swapData(u, v);
        this.deleteNode(u);

        // find node that replaces a deleted node in BST
        function BSTreplace(x: RBTreeNode<T>): RBTreeNode<T> | null {
            // when node have 2 children
            if (x.left && x.right) return successor(x.right);
            // when leaf
            if (!x.left && !x.right) return null;
            // when single child
            return x.left ?? x.right;
        }
        // find node that do not have a left child
        // in the subtree of the given node
        function successor(x: RBTreeNode<T>): RBTreeNode<T> {
            let temp = x;
            while (temp.left) temp = temp.left;
            return temp;
        }
    }

    fixDoubleBlack(x: RBTreeNode<T>): void {
        if (x === this.root) return; // Reached root

        const sibling = x.sibling();
        const parent = x.parent!;
        if (!sibling) {
            // No sibiling, double black pushed up
            this.fixDoubleBlack(parent);
        } else {
            if (sibling.color === 0) {
                // Sibling red
                parent.color = 0;
                sibling.color = 1;
                if (sibling.isOnLeft()) this.rotateRight(parent);
                // left case
                else this.rotateLeft(parent); // right case
                this.fixDoubleBlack(x);
            } else {
                // Sibling black
                if (sibling.hasRedChild()) {
                    // at least 1 red children
                    if (sibling.left && sibling.left.color === 0) {
                        if (sibling.isOnLeft()) {
                            // left left
                            sibling.left.color = sibling.color;
                            sibling.color = parent.color;
                            this.rotateRight(parent);
                        } else {
                            // right left
                            sibling.left.color = parent.color;
                            this.rotateRight(sibling);
                            this.rotateLeft(parent);
                        }
                    } else {
                        if (sibling.isOnLeft()) {
                            // left right
                            sibling.right!.color = parent.color;
                            this.rotateLeft(sibling);
                            this.rotateRight(parent);
                        } else {
                            // right right
                            sibling.right!.color = sibling.color;
                            sibling.color = parent.color;
                            this.rotateLeft(parent);
                        }
                    }
                    parent.color = 1;
                } else {
                    // 2 black children
                    sibling.color = 0;
                    if (parent.color === 1) this.fixDoubleBlack(parent);
                    else parent.color = 1;
                }
            }
        }
    }

    insert(data: T): boolean {
        // search for a position to insert
        let parent = this.root;
        while (parent) {
            if (this.lt(data, parent.data)) {
                if (!parent.left) break;
                else parent = parent.left;
            } else if (this.lt(parent.data, data)) {
                if (!parent.right) break;
                else parent = parent.right;
            } else break;
        }

        // insert node into parent
        const node = new RBTreeNode(data);
        if (!parent) this.root = node;
        else if (this.lt(node.data, parent.data)) parent.left = node;
        else if (this.lt(parent.data, node.data)) parent.right = node;
        else {
            parent.count++;
            return false;
        }
        node.parent = parent;
        this.fixAfterInsert(node);
        return true;
    }

    search(predicate: (val: T) => boolean, direction: 'left' | 'right'): T | undefined {
        let p = this.root;
        let result = null;
        while (p) {
            if (predicate(p.data)) {
                result = p;
                p = p[direction];
            } else {
                p = p[direction === 'left' ? 'right' : 'left'];
            }
        }
        return result?.data;
    }

    find(data: T): RBTreeNode<T> | null {
        let p = this.root;
        while (p) {
            if (this.lt(data, p.data)) {
                p = p.left;
            } else if (this.lt(p.data, data)) {
                p = p.right;
            } else break;
        }
        return p ?? null;
    }

    count(data: T): number {
        const node = this.find(data);
        return node ? node.count : 0;
    }

    *inOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
        if (!root) return;
        for (const v of this.inOrder(root.left!)) yield v;
        yield root.data;
        for (const v of this.inOrder(root.right!)) yield v;
    }

    *reverseInOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
        if (!root) return;
        for (const v of this.reverseInOrder(root.right!)) yield v;
        yield root.data;
        for (const v of this.reverseInOrder(root.left!)) yield v;
    }
}

class TreeMap<K = number, V = unknown> {
    _size: number;
    tree: RBTree<K>;
    map: Map<K, V> = new Map();
    compare: Compare<K>;
    constructor(
        collection: Array<[K, V]> | Compare<K> = [],
        compare: Compare<K> = (l: K, r: K) => (l < r ? -1 : l > r ? 1 : 0),
    ) {
        if (typeof collection === 'function') {
            compare = collection;
            collection = [];
        }
        this._size = 0;
        this.compare = compare;
        this.tree = new RBTree(compare);
        for (const [key, val] of collection) this.set(key, val);
    }

    size(): number {
        return this._size;
    }

    has(key: K): boolean {
        return !!this.tree.find(key);
    }

    get(key: K): V | undefined {
        return this.map.get(key);
    }

    set(key: K, val: V): boolean {
        const successful = this.tree.insert(key);
        this._size += successful ? 1 : 0;
        this.map.set(key, val);
        return successful;
    }

    delete(key: K): boolean {
        const deleted = this.tree.deleteAll(key);
        this._size -= deleted ? 1 : 0;
        return deleted;
    }

    ceil(target: K): [K, V] | undefined {
        return this.toKeyValue(this.tree.search(key => this.compare(key, target) >= 0, 'left'));
    }

    floor(target: K): [K, V] | undefined {
        return this.toKeyValue(this.tree.search(key => this.compare(key, target) <= 0, 'right'));
    }

    higher(target: K): [K, V] | undefined {
        return this.toKeyValue(this.tree.search(key => this.compare(key, target) > 0, 'left'));
    }

    lower(target: K): [K, V] | undefined {
        return this.toKeyValue(this.tree.search(key => this.compare(key, target) < 0, 'right'));
    }

    first(): [K, V] | undefined {
        return this.toKeyValue(this.tree.inOrder().next().value);
    }

    last(): [K, V] | undefined {
        return this.toKeyValue(this.tree.reverseInOrder().next().value);
    }

    shift(): [K, V] | undefined {
        const first = this.first();
        if (first === undefined) return undefined;
        this.delete(first[0]);
        return first;
    }

    pop(): [K, V] | undefined {
        const last = this.last();
        if (last === undefined) return undefined;
        this.delete(last[0]);
        return last;
    }

    toKeyValue(key: K): [K, V];
    toKeyValue(key: undefined): undefined;
    toKeyValue(key: K | undefined): [K, V] | undefined;
    toKeyValue(key: K | undefined): [K, V] | undefined {
        return key != null ? [key, this.map.get(key)!] : undefined;
    }

    *[Symbol.iterator](): Generator<[K, V], void, void> {
        for (const key of this.keys()) yield this.toKeyValue(key);
    }

    *keys(): Generator<K, void, void> {
        for (const key of this.tree.inOrder()) yield key;
    }

    *values(): Generator<V, undefined, void> {
        for (const key of this.keys()) yield this.map.get(key)!;
        return undefined;
    }

    *rkeys(): Generator<K, undefined, void> {
        for (const key of this.tree.reverseInOrder()) yield key;
        return undefined;
    }

    *rvalues(): Generator<V, undefined, void> {
        for (const key of this.rkeys()) yield this.map.get(key)!;
        return undefined;
    }
}

/**
 * Your MyCalendar object will be instantiated and called as such:
 * var obj = new MyCalendar()
 * var param_1 = obj.book(startTime,endTime)
 */

type MyCalendar struct {
	rbt *redblacktree.Tree
}

func Constructor() MyCalendar {
	return MyCalendar{
		rbt: redblacktree.NewWithIntComparator(),
	}
}

func (this *MyCalendar) Book(startTime int, endTime int) bool {
	if p, ok := this.rbt.Ceiling(startTime + 1); ok && p.Value.(int) < endTime {
		return false
	}
	this.rbt.Put(endTime, startTime)
	return true
}

/**
 * Your MyCalendar object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Book(startTime,endTime);
 */

Rust

use std::collections::BTreeMap;

struct MyCalendar {
    tm: BTreeMap<i32, i32>,
}

impl MyCalendar {
    fn new() -> Self {
        MyCalendar {
            tm: BTreeMap::new(),
        }
    }

    fn book(&mut self, start_time: i32, end_time: i32) -> bool {
        if let Some((&key, &value)) = self.tm.range(start_time + 1..).next() {
            if value < end_time {
                return false;
            }
        }
        self.tm.insert(end_time, start_time);
        true
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Brute Force with List	Time Complexity: O(N) per booking. Space Complexity: O(N).
Approach 2: Balanced Tree Using TreeMap	Time Complexity: O(log N) per booking using SortedDict. Space Complexity: O(N).
Ordered Set	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force with List	O(n) per booking	O(n)	Simple implementation or small number of bookings
Balanced Tree (TreeMap / Ordered Map)	O(log n) per booking	O(n)	Large number of bookings where efficient neighbor lookup is required

Frequently asked questions

Is My Calendar I easy or hard?

My Calendar I is classified as Medium difficulty. The brute force solution is straightforward, but identifying the optimal ordered map approach and handling interval edge cases requires a solid understanding of search trees and interval logic.

My Calendar I Python/Java solution

Python solutions typically simulate an ordered structure with sorted lists or libraries like bisect, while Java solutions use TreeMap for efficient floor and ceiling queries. Both implementations achieve O(log n) insertion and overlap checks when using an ordered map.

How to solve My Calendar I in O(log n)?

Store events in a balanced ordered map keyed by start time. For a new interval, find the previous event using a floor lookup and ensure its end time does not exceed the new start. Then check the next event using a ceiling lookup to ensure its start is not before the new end. These operations run in O(log n).

What is the best approach for My Calendar I?

The balanced tree approach using TreeMap or an ordered map is the most efficient and commonly expected solution. By storing events sorted by start time, you only check the immediate previous and next intervals for overlap. Each booking runs in O(log n) time with O(n) space for storing events.

Is My Calendar I asked at Google/Amazon/Meta?

My Calendar I and its follow‑ups appear frequently in system design and data structure interviews at companies like Google, Amazon, and Meta. Interviewers use it to test interval overlap detection and familiarity with ordered data structures.

What data structure is used in My Calendar I?

Common implementations use a list of intervals for the brute force solution or a balanced binary search tree such as TreeMap, ordered map, or ordered set. These structures allow efficient neighbor searches when inserting new intervals.

What is the time complexity of My Calendar I?

The brute force list approach takes O(n) time per booking because it scans every existing event to check for overlap. Using a balanced tree like TreeMap reduces this to O(log n) per booking since it only checks neighboring intervals in the sorted structure.

My Calendar I solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Brute Force with List

Approach 2: Approach 2: Balanced Tree Using TreeMap

Approach 3: Ordered Set

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

My Calendar I solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Brute Force with List

Approach 2: Approach 2: Balanced Tree Using TreeMap

Approach 3: Ordered Set

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems