Free lesson · DSA Mastery - Interview Prep, End to End

My Calendar I

Medium8 min readdsabst-ordered-set

My Calendar I

My Calendar I opens the Ordered Set Applications sub-group and shifts from raw trees to the ordered-map abstraction: implement a booking system that accepts a new event [start, end) only if it doesn't overlap any existing booking. The clean solution keeps bookings in an ordered map (a TreeMap, internally a balanced BST) keyed by start time, using floor and ceiling queries to find the nearest bookings on either side and check them for overlap in O(log n). It's where the section's theory pays off: instead of manipulating a raw BST, you reach for the ordered-set/map your language provides and let its O(log n) order queries do the work. We present the ordered-map floor/ceiling solution (canonical), with the linear-scan baseline for contrast.

The insight: a new interval can only overlap the booking that starts just before it or the one that starts just after it - its immediate neighbors in start-time order. An ordered map gives those neighbors directly: floorKey(start) is the latest booking starting at or before the new start, and ceilingKey(start) is the earliest starting at or after. Checking just those two for overlap is enough; no need to scan all bookings. This is the floor/ceiling order query that defines an ordered map's value over a hash map.

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 start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.

Implement the MyCalendar class:

• MyCalendar() Initializes the calendar object.
• boolean book(int start, int end) 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.

Example 1:

MyCalendar cal = new MyCalendar();
cal.book(10, 20); // true
cal.book(15, 25); // false  (overlaps [10,20))
cal.book(20, 30); // true   ([20,30) does not overlap [10,20) since end is exclusive)

Constraints:

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

Approaches Overview

The linear scan checks the new interval against every existing booking - O(n) per call, O(n²) overall. The ordered-map approach stores bookings keyed by start time and checks only the two neighboring bookings (floor and ceiling of the new start) for overlap - O(log n) per call. With up to 1000 calls the scan passes, but the ordered map is the intended, scalable solution and the one that showcases ordered-set order queries.

Approach 1: Linear Scan - Baseline

The Idea

Keep a list of booked intervals. For each new [start, end), compare against every stored interval: they overlap iff start < existingEnd && existingStart < end. If any overlaps, reject; otherwise add the interval and accept.

Logic Flowchart

graph TD
    A["book(start, end)"] --> B["for each [s, e) in bookings"]
    B --> C{"start < e AND s < end?"}
    C -->|Yes| D["return false (overlap)"]
    C -->|No| B
    B --> E["add [start,end); return true"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the linear scan. The new interval is compared against every existing booking using the standard overlap test, rejecting on any overlap and otherwise adding it.

Complexity

Time: O(n) per book, O(n²) total. Space: O(n).

Approach 2: Ordered Map Floor/Ceiling - Canonical

The Idea

Store bookings in a TreeMap<Integer, Integer> mapping start -> end. For a new [start, end): look up floorKey(start) (the booking starting at or before start) - if it exists and its end is > start, they overlap. Look up ceilingKey(start) (the booking starting at or after start) - if it exists and its start is < end, they overlap. If neither overlaps, insert start -> end and return true.

Logic Flowchart

graph TD
    A["book(start, end)"] --> B["prev = floorKey(start)"]
    B --> C{"prev exists AND map[prev] > start?"}
    C -->|Yes| D["return false"]
    C -->|No| E["next = ceilingKey(start)"]
    E --> F{"next exists AND next < end?"}
    F -->|Yes| D
    F -->|No| G["put(start, end); return true"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the ordered-map approach. We check the booking just before the new start and the booking just after it for overlap, inserting the new interval only if neither neighbor conflicts.

Code

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

    public boolean book(int start, int end) {
        Integer prev = calendar.floorKey(start);    // latest booking starting <= start
        if (prev != null && calendar.get(prev) > start) return false;  // prev overlaps

        Integer next = calendar.ceilingKey(start);  // earliest booking starting >= start
        if (next != null && next < end) return false;                  // next overlaps

        calendar.put(start, end);
        return true;
    }
}

// Usage:
// book(10,20) -> true; book(15,25) -> false; book(20,30) -> true

This Java code uses a TreeMap of start to end. It checks the floor and ceiling neighbors of the new start for overlap, inserting the interval only when neither conflicts.

Step-by-Step Walkthrough

A frame-by-frame trace on the example sequence:

graph LR
    F0["book(10,20): map empty, no neighbors → insert; true"]
    F1["book(15,25): floor(15)=10, map[10]=20 > 15 → overlap → false"]
    F2["book(20,30): floor(20)=10, map[10]=20 > 20? no. ceiling(20)=none → insert; true"]
    F3["calendar = {10:20, 20:30}"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F1 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough runs the bookings. Ten to twenty inserts. Fifteen to twenty-five overlaps its floor neighbor and is rejected. Twenty to thirty has no conflicting neighbor and inserts.

Result: true, false, true.

Complexity

Time: O(log n) per book. Space: O(n).

Complexity Comparison

The ordered map is the intended solution: by checking only the two neighbors of the new start, it reduces each booking to O(log n). The linear scan is acceptable for 1000 calls but doesn't scale; the ordered-map approach generalizes to far larger inputs and demonstrates why ordered-set order queries (floor/ceiling) exist.

Variations & Follow-ups

Why is checking only the floor and ceiling neighbors sufficient?

Bookings are kept sorted by start time, and (since none overlap) they're disjoint intervals in increasing order. A new interval [start, end) can only collide with a booking whose start is just below start (it might extend past start) or just at/above start (it might begin before end). Any booking starting much earlier ends before the floor neighbor's start (intervals are disjoint and ordered), so it can't reach start; any starting much later begins after the ceiling neighbor, so it's past end. Thus the only two candidates for overlap are the immediate neighbors - the floor and ceiling of start - and checking them covers all possibilities.

Why does the half-open interval [start, end) matter for the overlap test?

Half-open means a booking occupies times start <= x < end, so end itself is free. Two intervals overlap only if they share an interior point: [a,b) and [c,d) overlap iff a < d && c < b (strict inequalities). This is why book(20, 30) succeeds against [10, 20) - the first ends at 20 (exclusive), and the second starts at 20, so they touch but don't overlap. Using <= instead of < would wrongly reject adjacent bookings. The exclusive end is what lets back-to-back events coexist, and the strict comparisons in the neighbor checks encode it.

Why use a TreeMap (ordered map) rather than a HashMap?

A HashMap gives O(1) lookup by exact key but has no order - it cannot answer "what's the booking just before/after this start time?" The whole solution hinges on those floor/ceiling neighbor queries, which require the keys to be ordered. A TreeMap (a balanced BST internally) maintains keys in sorted order and supports floorKey/ceilingKey in O(log n). This is the canonical case where an ordered map is essential and a hash map is useless: the moment you need nearest-key or range queries, you need the ordering. It's the lesson the whole section builds toward.

How does this set up the harder My Calendar II and III?

My Calendar I forbids any overlap (max 1 booking at a time). My Calendar II allows double-booking but forbids triple-booking, and My Calendar III asks for the maximum number of concurrent bookings at any time. Those require counting how many intervals cover each point, typically via a sweep over interval endpoints stored in an ordered map (a "difference array" on an ordered map: +1 at each start, −1 at each end, then track the running maximum). My Calendar I's neighbor-check approach doesn't directly extend to counting overlaps, which is why the next problem introduces the boundary-counting technique.

What about edge cases?

• First booking: No neighbors; always accepted.
• Adjacent bookings: [10,20) then [20,30) - touch at 20 but don't overlap; both accepted.
• Identical interval booked twice: The second overlaps the first; rejected.
• New interval fully containing or contained by another: Detected by the neighbor check (one of floor/ceiling overlaps).

Common Interview Pitfalls

• Using <= in the overlap test. Half-open intervals need strict <; otherwise adjacent bookings are wrongly rejected.
• Checking only one neighbor. Both the floor and the ceiling of the new start can overlap; check both.
• Reaching for a HashMap. Order queries require an ordered map; a hash map can't do floor/ceiling.
• Inserting before validating. Only put after confirming no overlap, or a rejected booking pollutes the map.

Why This Topic Matters

My Calendar I is where the section's ordered-map abstraction pays off: instead of hand-rolling a BST, you reach for the library's balanced-BST-backed ordered map and let floorKey/ceilingKey answer neighbor queries in O(log n). It crystallizes the rule from the introduction - the moment you need order (nearest-key, range), an ordered set/map is the right tool and a hash map can't help. The neighbor-overlap insight is also a staple of interval problems generally.

The next topic, My Calendar II, raises the stakes: allow double-booking but reject any event that would create a triple-booking (three events overlapping at some point). The neighbor check no longer suffices because you must count overlaps, so the clean approach uses an ordered map as a boundary counter - incrementing at each event start and decrementing at each end - and sweeps the affected range to check whether any point would reach a count of three. It generalizes the calendar problem from "any overlap" to "count overlaps," introducing the ordered-map sweep that underlies a whole family of interval-counting problems.

Back to DSA Mastery - Interview Prep, End to End