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

My Calendar II

Medium8 min readdsabst-ordered-set

My Calendar II

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 from My Calendar I 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 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. We present the ordered-map boundary-counting solution (canonical), with the two-list overlap-tracking approach as an alternative.

The insight: the number of events active at any instant equals the running sum of +1 at every start and −1 at every end, scanned in time order. An ordered map keyed by time stores these deltas, automatically sorted. To test a new booking, tentatively add its +1/−1, sweep the running count across the timeline, and if it ever reaches 3, the booking would cause a triple-booking - reject and undo. This boundary-counting (sweep-line) technique counts overlaps that a mere neighbor check cannot.

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 triple booking.

A triple booking happens when three events have some non-empty intersection (i.e., some moment is common to all three 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).

Implement the MyCalendarTwo class:

MyCalendarTwo() Initializes the calendar object.
boolean book(int start, int end) Returns true if the event can be added without causing a triple booking. Otherwise return false and do not add the event.

Example 1:

MyCalendarTwo cal = new MyCalendarTwo();
cal.book(10, 20); // true
cal.book(50, 60); // true
cal.book(10, 40); // true   (double-books [10,20))
cal.book(5, 15);  // false  (would triple-book [10,15))
cal.book(5, 10);  // true
cal.book(25, 55); // true

Constraints:

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

Approaches Overview

#	Approach	Time per book	Space	Verdict
1	Two lists: all bookings + overlaps	O(n)	O(n)	Alternative
2	Ordered-map boundary counting (sweep)	O(n log n)	O(n)	Canonical

The two-list approach keeps every booking and, separately, every overlap region; a new event is rejected if it intersects any existing overlap (that would be a triple). The ordered-map approach stores +1/−1 deltas at event boundaries and sweeps the running count, rejecting if it reaches 3. Both are O(n) per call in the worst case; the ordered-map sweep generalizes cleanly to "no k-booking" and is the canonical technique.

Approach 1: Two Lists - All Bookings + Overlaps - Alternative

The Idea

Maintain two lists: bookings (all accepted intervals) and overlaps (regions already double-booked). For a new [start, end): first, if it intersects any interval in overlaps, it would form a triple - reject. Otherwise, for each existing booking it intersects, compute the intersection and add that to overlaps. Finally add the new interval to bookings and accept.

Logic Flowchart

graph TD
    A["book(start, end)"] --> B["for each o in overlaps"]
    B --> C{"intersects o?"}
    C -->|Yes| D["return false (triple)"]
    C -->|No| B
    B --> E["for each b in bookings: add intersection to overlaps"]
    E --> F["add [start,end) to bookings; 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:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the two-list approach. A new event is rejected if it intersects any existing double-booked region; otherwise its intersections with current bookings become new overlaps and the event is stored.

Complexity

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

Approach 2: Ordered-Map Boundary Counting - Canonical

The Idea

Keep a TreeMap<Integer, Integer> of time -> delta. To book [start, end), tentatively do delta[start]++ and delta[end]--. Then sweep the map in key (time) order, accumulating a running active count; if it ever reaches 3, undo the two deltas and return false. Otherwise the booking is safe - leave the deltas in place and return true. The running sum at any time equals the number of events covering that instant.

Logic Flowchart

graph TD
    A["book(start, end)"] --> B["delta[start]++; delta[end]--"]
    B --> C["active = 0"]
    C --> D["for each delta d in time order: active += d"]
    D --> E{"active >= 3?"}
    E -->|Yes| F["undo deltas; return false"]
    E -->|No| D
    D --> G["return true"]

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

This flowchart shows the boundary-counting sweep. We tentatively add plus one at the start and minus one at the end, then accumulate the running active count over time; if it reaches three we undo and reject, otherwise we accept.

Code

class MyCalendarTwo {
    private final TreeMap<Integer, Integer> delta = new TreeMap<>();

    public boolean book(int start, int end) {
        delta.merge(start, 1, Integer::sum);     // tentative +1 at start
        delta.merge(end, -1, Integer::sum);      // tentative -1 at end

        int active = 0;
        for (int d : delta.values()) {           // sweep in time order
            active += d;
            if (active >= 3) {                   // would be a triple booking
                delta.merge(start, -1, Integer::sum);   // undo
                delta.merge(end, 1, Integer::sum);
                return false;
            }
        }
        return true;
    }
}

// Usage:
// book(10,20)=T, book(50,60)=T, book(10,40)=T, book(5,15)=F, book(5,10)=T, book(25,55)=T

This Java code stores plus-one and minus-one deltas at event boundaries in a TreeMap, sweeps the running active count in time order, and rejects with an undo if the count reaches three.

Step-by-Step Walkthrough

A frame-by-frame trace focusing on book(5, 15) after [10,20), [50,60), [10,40) are booked:

graph LR
    F0["existing deltas: 10:+2, 20:-1, 40:-1, 50:+1, 60:-1"]
    F1["tentative book(5,15): add 5:+1, 15:-1"]
    F2["sweep: t5→1, t10→1+2=3 → active hits 3"]
    F3["triple at [10,15) → undo 5 and 15 deltas → return false"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F2 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F3 fill:#dc2626,stroke:#ef4444,color:#f1f5f9

This walkthrough tests booking five to fifteen. Adding its deltas and sweeping, the active count reaches three at time ten, signaling a triple booking, so the deltas are undone and the booking is rejected.

Result: book(5, 15) returns false.

Complexity

Time: O(n log n) per book (sweep over the map). Space: O(n).

Complexity Comparison

Approach	Time per book	Space	Key Idea	When to Use
Two lists	O(n)	O(n)	Reject if intersecting an overlap	Compact, no sweep
Ordered-map boundary counting	O(n log n)	O(n)	Sweep running count of active events	Canonical / generalizes

Both work within the constraints. The two-list approach is slightly faster per call but specific to the "no triple" rule. The ordered-map sweep is the canonical technique: it counts concurrent events directly and generalizes immediately to "no k-booking" (reject when the count reaches k) and to My Calendar III (report the running maximum).

Variations & Follow-ups

Why does a running sum of +1/−1 deltas count concurrent events?

Each event contributes +1 to the active count from its start onward and −1 from its end onward; summed over time, these deltas reconstruct exactly how many events are "open" at any instant. Scanning the boundary points in time order and accumulating gives the active count in each gap between boundaries - it rises by 1 when an event starts and falls by 1 when one ends. The maximum of this running count over the timeline is the peak concurrency. This sweep-line / difference-array idea turns "how many intervals cover this point?" into a simple prefix sum over sorted boundaries.

Why must the sweep happen in time order, and why an ordered map?

The running count only makes sense if boundaries are processed chronologically - a +1 at an earlier start must be counted before a −1 at a later end. An ordered map keyed by time keeps the boundaries sorted automatically, so iterating its entries yields them in time order for free. A hash map would store the same deltas but in no particular order, making the sweep impossible without first sorting. As in My Calendar I, the need for ordered iteration over keys is exactly what mandates an ordered map over a hash map.

Why tentatively apply the deltas and then undo on rejection?

Applying the new event's +1/−1 before sweeping lets the single sweep account for the new event alongside the existing ones - the check "does any point reach 3?" then directly answers "would this booking cause a triple?" If the sweep finds a triple, the event must not be recorded, so you undo the two deltas to restore the map to its prior state, leaving it as if the booking never happened. This tentative-apply-then-maybe-undo pattern keeps the data structure consistent while letting you reuse the same sweep logic for the test and the commit. Forgetting to undo would corrupt future bookings.

How does this extend to My Calendar III (max concurrent bookings)?

My Calendar III asks for the maximum number of simultaneous events after each booking, never rejecting any. The same ordered-map delta structure applies: every booking permanently adds its +1/−1, and after each call you sweep the running count and return its maximum. There's no undo because nothing is rejected. So My Calendar I (no overlap), II (no triple), and III (report max) form a ladder: neighbor check → bounded sweep with undo → unbounded sweep reporting the peak. The boundary-counting technique scales across all three by changing only the acceptance rule.

What about edge cases?

Half-open boundaries: A −1 at one event's end and a +1 at another's equal start net to zero at that instant, so back-to-back events don't falsely count as concurrent.
First bookings: Count never reaches 3 until a third overlap exists.
Identical intervals booked twice: Allowed (double-booking); a third identical would be rejected.
Undo correctness: After rejection, the map must equal its pre-call state.

Common Interview Pitfalls

Using >= 3 vs > 2 inconsistently, or wrong threshold. Reject when the active count reaches 3.
Forgetting to undo after rejection. The tentative deltas must be removed so the map stays correct.
Hash map instead of ordered map. The sweep needs time-ordered boundaries.
Mishandling the half-open end. Decrement at end (exclusive) so adjacent events don't overlap.

Why This Topic Matters

My Calendar II introduces the ordered-map boundary-counting sweep - the workhorse for counting how many intervals cover each point. It generalizes the calendar from "any overlap" to "count overlaps," and the +1/−1 delta technique over an ordered map is foundational for interval scheduling, concurrency peaks, and resource-usage problems. The tentative-apply-then-undo pattern is a clean, reusable way to test a mutation before committing it.

The next topic, Stock Price Fluctuation, closes the section with a different ordered-set application: a stream of timestamped stock-price updates (where a timestamp's price can be corrected later) must support querying the current price (latest timestamp), the maximum price, and the minimum price - all efficiently as updates arrive. The clean design pairs a hash map (timestamp -> price, for corrections and finding the latest) with an ordered multiset of prices (a TreeMap of price -> count) so that max and min are the ordered structure's extremes in O(log n), updated as prices are corrected. It's a capstone that combines hashing for direct lookup with an ordered structure for min/max - exactly the hybrid that real systems use - before the course moves on to Tries.

Back to DSA Mastery - Interview Prep, End to End