Problem 36.5 · Advanced Data StructuresMedium

My Calendar I

PatternRange Queries (Fenwick & Segment Trees)Combine Structures to Design BST Ordering

What it teaches: An ordered map answers "does this overlap the nearest bookings?" in O(log n).

Practise it on judges as “My Calendar I”.

In plain words

You're filling a diary. A new booking is allowed only if it doesn't overlap any existing one. Keep bookings sorted by start time; then you only need to check two neighbours: the booking that starts just before the new one, and the one that starts just after.

Return true or false for each booking. Example: book(10, 20), book(15, 25), book(20, 30) → true, false, true.

The problem

Design MyCalendar with book(start, end) for the half-open interval [start, end). Return true and store it if it doesn't overlap an existing booking, otherwise false.

Example 1

Input: book(10, 20), book(15, 25), book(20, 30)
Output: true, false, true

Constraints

Up to 1000 calls
0 ≤ start < end ≤ 10⁹

Pattern clues in the wording

→ Dynamic intervals, check overlap on insert

These clues point to Range Queries (Fenwick & Segment Trees): Answer sums, minimums or counts over any range while the array keeps changing, in O(log n) per query and update.

Stuck? Take one hint at a time

MyCalendar · starter

import java.util.*;

class MyCalendar {
    public MyCalendar() {}
    public boolean book(int start, int end) { return false; }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	ops = ["MyCalendar","book","book","book"] args = [[],[10,20],[15,25],[20,30]]	[null,true,false,true]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. TreeMap start → end · O(log n) per booking

TreeMap start → end

Time O(log n) per booking Space O(n)

prev = floorEntry(start): must end ≤ start. next = ceilingKey(start): must be ≥ end.

▶ Dry run: Check the two neighboursbook(10, 20), book(15, 25), book(20, 30)

booked(map)

10: 20

answers(list)

true

Step 1/3book(10, 20): the diary is empty, so store it.

Approach 1

import java.util.*;

class MyCalendar {
    private final TreeMap<Integer, Integer> booked = new TreeMap<>();

    public MyCalendar() {}

    public boolean book(int start, int end) {
        Map.Entry<Integer, Integer> prev = booked.floorEntry(start);
        Integer next = booked.ceilingKey(start);
        if (prev != null && prev.getValue() > start) return false;
        if (next != null && next < end) return false;
        booked.put(start, end);
        return true;
    }
}

Verdict: Ordered map for a dynamic set of intervals.

Before you submit

Edge cases and common mistakes

Test these inputs

Touching intervals ([10, 20) and [20, 30) don't overlap)
Same start

Mistakes people make

Checking every stored booking (O(n) per call).

Interview

Follow-up questions

What if double bookings are allowed but not triple (My Calendar II)?

Connect the dots

Where this shows up in real systems

System Design · System 12.38 — Hotel Reservation SystemChecking a new booking against existing ones with a sorted map.

Command Palette