My Calendar III

Problem

LeetCode 732 — My Calendar III

Implement MyCalendarThree which tracks calendar bookings. Each book(start, end) adds an event on [start, end) (half-open interval). Return the maximum number of events that overlap at any single point in time after each booking.

Example

book(10, 20)  →  1
book(50, 60)  →  1
book(10, 40)  →  2   (overlap on [10, 20))
book(5, 15)   →  3   (overlap on [10, 15))

Timeline after all four bookings:

        5    10   15   20        40   50        60
        [-----)                           (book 4: [5,15))
             [-----)                     (book 1: [10,20))
             [-------------------)        (book 3: [10,40))
                                      [-----)  (book 2: [50,60))

        At [10, 15): events 1, 3, and 4 overlap → peak = 3

Approach — Sweep Line with TreeMap

Each booking adds +1 at start and -1 at end on a timeline — same idea as Meeting Rooms II’s sweep, but you track the peak overlap instead of the current count at one moment.

timeline[start] += 1
timeline[end]   -= 1

sweep keys in sorted order:
    active += timeline[t]
    max = max(max, active)

Half-open intervals [start, end) mean the -1 at end correctly removes the event before time end is counted as active.

Why TreeMap? Times go up to 10⁹, but only ~400 bookings — endpoints are sparse. TreeMap keeps sorted event points without a huge array.

Why not increment every minute in [start, end)? Range can be billions wide — marking only boundaries avoids a huge array.

Walkthrough (example order)

After book(10, 20):
  timeline: 10:+1, 20:-1  →  sweep: active 1 at 10, max = 1

After book(50, 60):
  timeline: 10:+1, 20:-1, 50:+1, 60:-1  →  max still 1

After book(10, 40):
  timeline: 10:+2, 20:-1, 40:-1, 50:+1, 60:-1
  sweep: 10→2, 20→1, 40→0, 50→1, 60→0  →  max = 2

After book(5, 15):
  timeline: 5:+1, 10:+2, 15:-1, 20:-1, 40:-1, 50:+1, 60:-1
  sweep: 5→1, 10→3, 15→2, 20→1, 40→0, 50→1, 60→0  →  max = 3

At time 10, three events are active: [5,15), [10,20), and [10,40).

Complexity

• Time: O(k) sweep per book(), plus O(log k) for each TreeMap update — dominated by O(k) where k = distinct endpoints so far (≤ ~800 on LC)
• Space: O(k)

maxOverlap is never reset — each book() returns the peak overlap seen across all bookings so far, which matches the problem.

For point update + range query on a dense array, see 18-segment-tree-range-queries.md. Calendar booking is a range add — sweep line fits better here.

Solution

class MyCalendarThree {
    private final TreeMap<Integer, Integer> timeline = new TreeMap<>();
    private int maxOverlap = 0;

    public int book(int start, int end) {
        timeline.put(start, timeline.getOrDefault(start, 0) + 1);
        timeline.put(end, timeline.getOrDefault(end, 0) - 1);

        int active = 0;
        for (int delta : timeline.values()) {
            active += delta;
            maxOverlap = Math.max(maxOverlap, active);
        }
        return maxOverlap;
    }
}

Why It Teaches You Something

Same family as #12 (intervals + time sweep), different question: peak overlap vs greedy scheduling.

The difference-array-on-endpoints trick is the interview solution here.