My Calendar II

MediumOrdered Set · Intervals · Design🧩 Ordered Set (TreeMap)LeetCode #731 ↗Updated Oct 30, 2026

Problem

Implement MyCalendarTwo whose book(start, end) tries to add the half-open event [start, end). Two events may overlap (a double booking), but the call must be rejected (return false, store nothing) if the new event would make some moment covered by three events. Otherwise store it and return true.

Inputbook(10,20) book(50,60) book(10,40)Outputtrue, true, true

Inputbook(5,15) book(5,10) book(25,55)Outputfalse, true, true

0 ≤ start < end ≤ 10⁹ · at most 1000 calls to book

Try it yourself

Java

class MyCalendarTwo {
    public boolean book(int start, int end) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

A booking fails exactly when some point of [start, end) is already covered twice. So keep track of the double-booked regions (or the max coverage over a range) — you never need to enumerate triples.

PatternOrdered Set (TreeMap)

Instinct Keys keep arriving or leaving and you must ask "what is the nearest key below/above x?" or "current min/max" each time - reach for TreeMap/TreeSet.

Memory hack A HashMap with a sense of direction - floor looks down, ceiling looks up, and both answer in log time while the data keeps changing.

Open the Ordered Set (TreeMap) guide →

Approaches

Brute ForceCheck Every Pair of Bookings

Time O(n²) per bookSpace O(n)

A triple booking needs two stored events a, b whose common part with the new event is non-empty: max(starts) < min(ends). Try every pair; if none qualifies the event is safe to add.

Java

class MyCalendarTwo {
    private final List<int[]> bookings = new ArrayList<>();

    public boolean book(int start, int end) {
        for (int i = 0; i < bookings.size(); i++) {
            int[] a = bookings.get(i);
            for (int j = i + 1; j < bookings.size(); j++) {
                int[] b = bookings.get(j);
                int lo = Math.max(start, Math.max(a[0], b[0]));
                int hi = Math.min(end, Math.min(a[1], b[1]));
                if (lo < hi) return false;   // all three share [lo, hi)
            }
        }
        bookings.add(new int[]{start, end});
        return true;
    }
}

Direct translation of the definition, but quadratic work per call.

BetterBookings + Overlap List

Time O(n) per bookSpace O(n)

Also store every double-booked region. If the new event intersects any of them, it would be the third → reject. Otherwise its intersections with the existing bookings become new overlaps. Overlaps never intersect each other (that would already be a triple), so the list stays O(n).

Java

class MyCalendarTwo {
    private final List<int[]> bookings = new ArrayList<>();
    private final List<int[]> overlaps = new ArrayList<>();

    public boolean book(int start, int end) {
        for (int[] o : overlaps) {
            if (start < o[1] && o[0] < end) return false;   // would be a triple
        }
        for (int[] b : bookings) {
            if (start < b[1] && b[0] < end) {
                overlaps.add(new int[]{Math.max(start, b[0]), Math.min(end, b[1])});
            }
        }
        bookings.add(new int[]{start, end});
        return true;
    }
}

Linear per call and simple — the expected interview answer.

OptimalDynamic Segment Tree (Range Add, Range Max)

Time O(log C) per bookSpace O(n log C)

Treat time [0, 10⁹] as a lazily-built segment tree where each node stores the max coverage in its range. Reject if max(start..end-1) ≥ 2, else add +1 on that range with a lazy tag. Only O(log C) nodes are touched or created per call (C = 10⁹).

Java

class MyCalendarTwo {
    private static final int MAX = 1_000_000_000;
    private final Node root = new Node();

    public boolean book(int start, int end) {
        if (query(root, 0, MAX, start, end - 1) >= 2) return false;
        update(root, 0, MAX, start, end - 1);
        return true;
    }

    private int query(Node node, int lo, int hi, int l, int r) {
        if (r < lo || hi < l) return 0;
        if (l <= lo && hi <= r) return node.max;
        push(node);
        int mid = lo + (hi - lo) / 2;
        return Math.max(query(node.left, lo, mid, l, r),
                        query(node.right, mid + 1, hi, l, r));
    }

    private void update(Node node, int lo, int hi, int l, int r) {
        if (r < lo || hi < l) return;
        if (l <= lo && hi <= r) { node.max++; node.lazy++; return; }
        push(node);
        int mid = lo + (hi - lo) / 2;
        update(node.left, lo, mid, l, r);
        update(node.right, mid + 1, hi, l, r);
        node.max = Math.max(node.left.max, node.right.max);
    }

    private void push(Node node) {   // create children, hand down pending +lazy
        if (node.left == null) { node.left = new Node(); node.right = new Node(); }
        node.left.max += node.lazy;  node.left.lazy += node.lazy;
        node.right.max += node.lazy; node.right.lazy += node.lazy;
        node.lazy = 0;
    }

    private static class Node { Node left, right; int max, lazy; }
}

Logarithmic per call and generalises to any k-booking limit.

Pro tip

A sweep line (TreeMap of +1 at start / −1 at end, prefix-sum and undo on failure) is a shorter O(n)-per-call alternative.

At a glance

Level	Approach	Time	Space
Brute Force	Check Every Pair of Bookings	`O(n²) per book`	`O(n)`
Better	Bookings + Overlap List	`O(n) per book`	`O(n)`
Optimal	Dynamic Segment Tree (Range Add, Range Max)	`O(log C) per book`	`O(n log C)`

Common pitfalls

Closed-interval checks — [10,20) and [20,30) do not overlap.
Recording overlaps before the triple check — a rejected call must leave no trace.
Rejecting when the new event overlaps two bookings that do not overlap each other.

Interview tips

Clarify half-open intervals and the 10⁹ range (rules out a plain array).
Explain why overlap regions are disjoint, so the list stays linear.
Mention the k-booking generalisation (My Calendar III) via sweep line or segment tree.

Pattern

Interval coverage counting → accept/reject intervals based on how many times a point is already covered.

My notes saved in this browser