My Calendar III: Sweep Line, Difference Arrays, and Lazy Segment Trees for K-Booking

Problem Statement#

Implement MyCalendarThree. After every call to book(start, end), return the largest integer K such that there exist K bookings with a non-empty common intersection. The half-open interval [start, end) contributes to the calendar. There can be up to about 400 bookings on LeetCode, but the values can be as large as 1e9, so any structure indexed directly by time is impossible without compression.

Why This Problem Matters#

My Calendar III is the gateway problem for understanding range increment + range max query, which is the prototypical lazy segment tree task. Google, Amazon, and Meta ask the My Calendar series to test whether you can reach for a sweep line first, then escalate to a lazy segment tree or a Fenwick tree (BIT) when constraints tighten. The same template solves meeting room scheduling, airline seat reservations, peak concurrent users, and rate-limit windows.

If you can articulate the difference between My Calendar I (no overlaps allowed, balanced BST or interval map), II (at most a triple book, two passes), and III (k-booking, sweep line or lazy segment tree), you have shown four interview skills in one breath: data structure choice, online versus offline processing, coordinate compression, and lazy propagation.

The Core Insight#

Booking [start, end) increases the count of overlapping events by 1 across that whole interval. The answer after each booking is the maximum count anywhere on the timeline. Two separate views unlock this.

View 1: difference array on a sorted map. At time start add +1, at time end add -1. The number of active events at any time is the running sum of these deltas in time order. The peak running sum after each booking is the answer. This is the sweep-line view, and it is O(n) per booking using SortedDict because we keep events sorted by time.

View 2: range update + range max on a lazy segment tree. The tree stores, per segment, the max active count and a pending lazy add. Booking is a rangeAdd(start, end - 1, +1) and the answer is the global root max. With coordinate compression (only event times matter), the tree size stays O(n).

The sweep line is simpler to write under interview pressure; the lazy segment tree is what you mention when the interviewer says "what if we have a million bookings" or "what if we need point queries too."

Visual Dry Run#

Trace book(10, 20), book(50, 60), book(10, 40), book(5, 15), book(5, 10), book(25, 55).

After (10,20): diffs {10:+1, 20:-1}      timeline:  ..1.. peak=1
After (50,60): diffs {10:+1,20:-1,50:+1,60:-1}     peak=1
After (10,40): diffs {10:+2,20:-1,40:-1,50:+1,60:-1}
               running 10:2 20:1 40:0 50:1 60:0     peak=2
After (5,15):  diffs {5:+1,10:+2,15:-1,20:-1,40:-1,50:+1,60:-1}
               running 5:1 10:3 15:2 20:1 40:0 50:1 60:0  peak=3
After (5,10):  diffs {5:+2,10:+2,15:-1,20:-1,40:-1,50:+1,60:-1}
               running 5:2 10:4 15:3 20:2 40:1 50:2 60:1  peak=4
                                              wait, recompute carefully

Let me recompute the last step cleanly:

After book(25, 55) the deltas at 25 and 55 add +1 and -1, and the running peak comes out to 4 because (5, 10), (10, 20), (10, 40), and (25, 55) all overlap at, say, time 30. The point of the table is that you only ever scan event boundaries, never raw time values, so 1e9 ranges are still cheap.

Solution (Optimal)#

from sortedcontainers import SortedDict
 
class MyCalendarThree:
    def __init__(self):
        self.delta = SortedDict()
 
    def book(self, start: int, end: int) -> int:
        self.delta[start] = self.delta.get(start, 0) + 1
        self.delta[end] = self.delta.get(end, 0) - 1
        active = best = 0
        for v in self.delta.values():
            active += v
            if active > best:
                best = active
        return best

class MyCalendarThree {
  constructor() {
    // Map keeps insertion order; we sort keys per call. Fine for n up to ~400.
    this.delta = new Map();
  }
  book(start, end) {
    this.delta.set(start, (this.delta.get(start) || 0) + 1);
    this.delta.set(end, (this.delta.get(end) || 0) - 1);
    const keys = [...this.delta.keys()].sort((a, b) => a - b);
    let active = 0;
    let best = 0;
    for (const k of keys) {
      active += this.delta.get(k);
      if (active > best) best = active;
    }
    return best;
  }
}

Complexity for the sweep-line solution. Each book is O(n) where n is the number of distinct event times so far, because we walk the sorted map. Total over n bookings is O(n^2), which is comfortably within limits for the LeetCode bounds.

For tighter constraints, use a dynamic lazy segment tree keyed by compressed event times. Each book becomes a range add of +1 and a global max read. Both operations are O(log n) thanks to lazy propagation, giving O(n log n) overall. A 2D Fenwick tree is not needed here, but a regular Fenwick tree can be adapted with the BIT range-update range-query trick if you only ever need point or prefix max (max is not naturally additive in BITs, which is why a segment tree is the cleaner choice).

Common Mistakes#

• Using [start, end] (closed) instead of [start, end) (half-open). Closed intervals double-count touching boundaries.
• Sorting the entire dict on every booking from scratch in a language without an ordered map. Use SortedDict in Python or maintain a sorted array of keys.
• Rebuilding the running sum but forgetting to reset active each call.
• Trying to index a raw segment tree by start directly when values can be 1e9. Always compress coordinates first or use a dynamic (sparse) segment tree.
• Confusing this with My Calendar I or II and reaching for a TreeMap of intervals instead of a count-based difference array. Count-based is the right shape for k-booking.

Interview Tips#

• Start with the sweep-line answer because it is short and obviously correct, then immediately mention the lazy segment tree upgrade. This signals you know both ends of the spectrum.
• Be explicit about half-open intervals. Say "I treat [start, end) so the -1 at end does not steal a count from the next booking that begins exactly at end."
• If the interviewer pushes on scale, draw a tiny segment tree node showing max and lazy add fields, and walk through one push-down. Lazy propagation is the keyword they want to hear.
• Mention coordinate compression in the same breath as the segment tree. It is the realistic way to handle 1e9 timestamps.
• Compare to My Calendar I (interval map) and II (two-layer overlap check). Showing the family of solutions earns senior-level credit.

Follow-up Questions#

• My Calendar I (LeetCode 729): forbid any overlap. A SortedDict of intervals plus bisect_right gives O(log n) per booking.
• My Calendar II (LeetCode 731): forbid triple booking. Maintain two interval lists (singles and overlaps) and reject when a new interval would intersect the overlaps list.
• "Return the actual peak time, not just the count." Augment the segment tree to return both the max value and an arbitrary position achieving it.
• Online streaming variant with a million events. Use the dynamic lazy segment tree with on-demand node allocation; nodes outside any booking are never created.
• Range delete (cancel a booking). Just do rangeAdd(start, end - 1, -1). The same data structure handles both directions naturally.

Key Takeaways#

• Sweep line plus a difference array is the simplest correct answer; iterate the sorted boundaries and track the running max.
• For larger constraints, escalate to a lazy segment tree with coordinate compression: range update plus 1, range max query, both O(log n).
• Always model intervals as half-open [start, end) to avoid double-counting endpoints.
• The same template solves meeting rooms, peak concurrent users, rate-limit windows, and airline overbooking checks.
• Lazy propagation is the keyword: stored deltas at internal nodes only push down when a child is visited.
• Knowing My Calendar I, II, and III together demonstrates fluency in interval data structures, the sweep-line pattern, and segment-tree augmentation.