My Calendar I

MediumProblemExternal linkUpdated Oct 31, 2026

Description

You are building a calendar. A new booking is added only if it causes no double booking: it must share no moment with any booking already made.

A booking is a pair of integers start and end, the half-open time [start, end): every x with start <= x < end. So a booking that ends at 20 and one that starts at 20 don't overlap.

Implement the MyCalendar class:

MyCalendar() makes an empty calendar.
boolean book(int start, int end) adds the booking and returns true if it overlaps none of the bookings made so far; otherwise it returns false and the calendar doesn't change.

Examples

Example 1

Input:

["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]

Output: [null, true, false, true]

Explanation:

MyCalendar(): an empty calendar.
book(10, 20): the calendar is empty; return true.
book(15, 25): overlaps [10, 20) between 15 and 20; return false.
book(20, 30): overlaps no booking; return true.

15 to 25 overlaps 10 to 20 between 15 and 20, so it is refused. 20 to 30 starts where 10 to 20 ends: an end isn't part of its booking, so the two touch without overlapping.

Example 2

Input:

["MyCalendar", "book", "book", "book", "book"]
[[], [10, 20], [5, 25], [12, 18], [5, 10]]

Output: [null, true, false, false, true]

Explanation:

MyCalendar(): an empty calendar.
book(10, 20): the calendar is empty; return true.
book(5, 25): overlaps [10, 20) between 10 and 20; return false.
book(12, 18): overlaps [10, 20) between 12 and 18; return false.
book(5, 10): overlaps no booking; return true.

5 to 25 swallows 10 to 20 whole, and 12 to 18 sits inside it: both refused. 5 to 10 ends where 10 to 20 begins, so it fits.

Example 3

Input:

["MyCalendar", "book", "book", "book", "book"]
[[], [0, 10], [20, 30], [10, 20], [9, 21]]

Output: [null, true, true, true, false]

Explanation:

MyCalendar(): an empty calendar.
book(0, 10): the calendar is empty; return true.
book(20, 30): overlaps no booking; return true.
book(10, 20): overlaps no booking; return true.
book(9, 21): overlaps [0, 10) between 9 and 10; return false.

10 to 20 fills the gap between the first two exactly, touching both. 9 to 21 then overlaps all three.

Constraints

0 ≤ start < end ≤ 10^9
At most 1000 calls will be made to book

Editorial

Brute Force

Intuition

Keep every booking in a list. Two bookings overlap exactly when each starts before the other ends: start < e and s < end. Check the new booking against every one in the list; if none overlaps, add it.

Step-by-Step Explanation

Let's trace book(10, 20), book(15, 25) and book(20, 30):

book(10, 20): nothing is booked yet: return true.
book(15, 25): it overlaps [10, 20) between 15 and 20: return false.
book(20, 30): it overlaps none of the 1 booking: return true.

Check Every Booking — The bookings made so far on top, the new one below; the shaded band is where they overlap.

Algorithm

Keep a list of bookings, empty at the start.
On book(start, end): for each booking (s, e), if start < e and s < end, return false.
Otherwise add (start, end) and return true.

Code

class MyCalendar {
    vector<pair<int, int>> booked;           // every booking so far
public:
    MyCalendar() {}

    bool book(int start, int end) {
        for (auto [s, e] : booked)
            if (start < e && s < end) return false;   // each starts before the other ends: they overlap
        booked.push_back({start, end});
        return true;
    }
};

class MyCalendar:
    def __init__(self):
        self.booked = []                     # every booking so far

    def book(self, start: int, end: int) -> bool:
        for s, e in self.booked:
            if start < e and s < end:        # each starts before the other ends: they overlap
                return False
        self.booked.append((start, end))
        return True

class MyCalendar {
    private final List<int[]> booked = new ArrayList<>();    // every booking so far

    public MyCalendar() {}

    public boolean book(int start, int end) {
        for (int[] b : booked)
            if (start < b[1] && b[0] < end) return false;   // each starts before the other ends: they overlap
        booked.add(new int[]{start, end});
        return true;
    }
}

var MyCalendar = function() {
    this.booked = [];                        // every booking so far
};

MyCalendar.prototype.book = function(start, end) {
    for (const [s, e] of this.booked)
        if (start < e && s < end) return false;   // each starts before the other ends: they overlap
    this.booked.push([start, end]);
    return true;
};

Complexity Analysis

Time Complexity: O(n) per call, O(n²) for n calls

The k-th call checks up to k − 1 bookings.

Space Complexity: O(n)

Every accepted booking is kept.

Why This Approach Is Not Efficient

Here it passes: at most 1,000 calls means at most about 500,000 checks. But the work per call grows with the calendar. Past this problem's limit, booking n slots that all fit, in random order, took 96.3 ms at n = 2,000 and 1,695 ms at n = 8,000 in Python: four times the bookings, 18 times the time. The sorted version below took 3.4 ms and 29.8 ms.

Most of those checks can't matter. The bookings already made never overlap each other, so sorted by start they are sorted by end too. A new booking can only overlap the last booking that starts at or before it, its floor, or the first one that starts after it, its ceiling. Everything before the floor ends before the floor does, and everything after the ceiling starts after it.

Optimal Approach - Check the Floor and the Ceiling

Intuition

Keep the bookings sorted by start. For a new [start, end), find where start would go:

The floor, the last booking starting at or before start, must end by start.
The ceiling, the first booking starting after start, must start at or after end.

If both hold, nothing else can overlap, so insert it there and the list stays sorted.

Step-by-Step Explanation

Let's trace the same three calls:

book(10, 20): it has no floor; it has no ceiling. Return true.
book(15, 25): its floor is [10, 20), which ends at 20, after 15: they overlap. Return false.
book(20, 30): its floor is [10, 20), which ends at 20, by 20; it has no ceiling. Return true.

Only the Floor and the Ceiling — The bookings sorted by start on top, the new one below. Amber marks the floor and the ceiling, the only two that can overlap it.

Algorithm

Keep the bookings sorted by start.
On book(start, end): find the floor and the ceiling of start.
If the floor ends after start, or the ceiling starts before end, return false.
Otherwise insert [start, end) between them and return true.

Code

Java's TreeMap and C++'s map are balanced binary search trees: floorEntry and ceilingKey, or upper_bound and the entry before it, find both neighbours in O(log n), and the insert is O(log n) too. Python and JavaScript have no sorted map built in, so their versions binary-search a sorted list for the neighbours and insert into it.

class MyCalendar {
    map<int, int> booked;                    // start → end, sorted by start
public:
    MyCalendar() {}

    bool book(int start, int end) {
        auto after = booked.upper_bound(start);                           // the first booking starting after start
        if (after != booked.end() && after->first < end) return false;
        if (after != booked.begin() && prev(after)->second > start) return false;   // the last one at or before start
        booked[start] = end;
        return true;
    }
};

from bisect import bisect_right

class MyCalendar:
    def __init__(self):
        self.starts = []                     # the bookings' starts, sorted
        self.ends = []                       # each start's end, at the same index

    def book(self, start: int, end: int) -> bool:
        i = bisect_right(self.starts, start)          # the bookings before i start at or before start
        if i > 0 and self.ends[i - 1] > start:        # the floor still runs at start
            return False
        if i < len(self.starts) and self.starts[i] < end:   # the ceiling begins before end
            return False
        self.starts.insert(i, start)                  # O(n): the list shifts
        self.ends.insert(i, end)
        return True

class MyCalendar {
    private final TreeMap<Integer, Integer> booked = new TreeMap<>();    // start → end, sorted by start

    public MyCalendar() {}

    public boolean book(int start, int end) {
        Map.Entry<Integer, Integer> floor = booked.floorEntry(start);     // the last booking starting at or before start
        if (floor != null && floor.getValue() > start) return false;
        Integer ceiling = booked.ceilingKey(start);                       // the first booking starting at or after start
        if (ceiling != null && ceiling < end) return false;
        booked.put(start, end);
        return true;
    }
}

var MyCalendar = function() {
    this.starts = [];                        // the bookings' starts, sorted
    this.ends = [];                          // each start's end, at the same index
};

MyCalendar.prototype.book = function(start, end) {
    let lo = 0, hi = this.starts.length;     // the first booking that starts after start
    while (lo < hi) {
        const mid = (lo + hi) >> 1;
        if (this.starts[mid] <= start) lo = mid + 1; else hi = mid;
    }
    if (lo > 0 && this.ends[lo - 1] > start) return false;                 // the floor still runs at start
    if (lo < this.starts.length && this.starts[lo] < end) return false;    // the ceiling begins before end
    this.starts.splice(lo, 0, start);        // O(n): the array shifts
    this.ends.splice(lo, 0, end);
    return true;
};

Complexity Analysis

Time Complexity: O(log n) per call in C++ and Java; O(n) per call in Python and JavaScript

The tree map finds the neighbours and inserts in O(log n). The sorted list finds them in O(log n), but the insert shifts every later booking, O(n), though it's a fast block move in memory.

Space Complexity: O(n)

Every accepted booking is kept once.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Treating a shared edge as an overlap. if start <= e and s <= end:

On book(10, 20), book(20, 30) it returns [true, false]; the answers are [true, true]. A booking is [start, end): the end isn't part of it. 10 to 20 and 20 to 30 share no moment, so both fit. Two bookings overlap only when each starts before the other ends: s1 < e2 and s2 < e1, strictly.

Checking only the floor. if i > 0 and self.ends[i - 1] > start:

On book(20, 30), book(10, 25) it returns [true, true]; the answers are [true, false]. The floor, the last booking that starts at or before start, can't overlap if it ends in time. But the next booking can still start before end: 20 to 30 is booked, and 10 to 25 has no floor at all. Check the ceiling too.

Checking only the ceiling. if i < len(self.starts) and self.starts[i] < end:

On book(10, 20), book(15, 25) it returns [true, true]; the answers are [true, false]. The ceiling, the first booking that starts after start, is half the check. The one before can still be running at start: 10 to 20 is booked, and 15 to 25 has no ceiling. Check the floor too.

Checking whether an end falls inside a booking. if s <= start < e or s < end <= e:

On book(10, 20), book(5, 25) it returns [true, true]; the answers are [true, false]. A new booking can swallow an old one whole: 5 to 25 around 10 to 20 has neither end inside it. Compare the two intervals, not the points: they overlap when each starts before the other ends.

Keeping a refused booking. self.booked.append((start, end))

On book(10, 20), book(15, 25), book(22, 30) it returns [true, false, false]; the answers are [true, false, true]. A refused booking changes nothing. Store it only after both checks pass, or a later booking that overlaps only the refused one is refused too.

Unboxing a missing floor in Java. int floor = booked.floorKey(start);

On book(10, 20) it throws a StringIndexOutOfBoundsException instead of returning [true]. floorKey and ceilingKey return null when there is no such booking, and the very first booking has neither. Assigning that null to an int throws a NullPointerException. Keep the Integer and check it for null.

Where This Pattern Is Taught

This problem practises floor and ceiling queries on an ordered set. It's taught in Balanced Trees and Ordered Sets, with the sorted sets and maps each language gives and why a balanced tree keeps them fast.