My Calendar III

hard intervals sweep line ordered map design

Problem

Design MyCalendarThree where book(start, end) records an event and returns the maximum k-booking (largest number of mutually overlapping events) across the calendar so far.

Inputbook(10,20); book(50,60); book(10,40); book(5,15)

Output[1, 1, 2, 3]

After the fourth booking, three events all contain time 10..15.

input

from sortedcontainers import SortedDict
class MyCalendarThree:
    def __init__(self):
        self.delta = SortedDict()
    def book(self, start, end):
        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() { 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, best = 0;
    for (const k of keys) { active += this.delta.get(k); if (active > best) best = active; }
    return best;
  }
}

class MyCalendarThree {
  TreeMap<Integer,Integer> delta = new TreeMap<>();
  public int book(int start, int end) {
    delta.merge(start, 1, Integer::sum);
    delta.merge(end, -1, Integer::sum);
    int active = 0, best = 0;
    for (int v : delta.values()) { active += v; if (active > best) best = active; }
    return best;
  }
}

class MyCalendarThree {
  map<int,int> delta;
public:
  int book(int start, int end) {
    delta[start]++; delta[end]--;
    int active = 0, best = 0;
    for (auto& [_, v] : delta) { active += v; if (active > best) best = active; }
    return best;
  }
};

Explanation

This problem asks, after each booking, for the maximum number of events that overlap at any single point in time. The elegant tool here is a difference map: at each event's start we add +1, and at its end we add -1.

Think of +1 as "one more event begins here" and -1 as "one event ends here." If we then walk through these time markers in sorted order and keep a running total, that total tells us how many events are active at that moment.

So for each booking we update delta[start] += 1 and delta[end] -= 1, then sweep all the keys from earliest to latest, accumulating into active and tracking the largest value in best. That best is the answer to return.

Example: after [10,20) and [50,60) the peak overlap is 1. Adding [10,40) makes times 10..20 have two active events, so the answer becomes 2. Adding [5,15) stacks a third event over 10..15, giving 3.

Keeping the deltas in a sorted map means the sweep always visits times in order, so the running sum correctly reflects the live overlap at every boundary.

Time: O(n) per booking Space: O(n)