My Calendar III

Problem Statement

Design a calendar that always accepts book(start, end) calls and returns the maximum number of concurrent events — the K in “K-booking” — after each call.

Input

Sequential calls to book(start, end), each an int pair denoting a half-open [start, end) interval.

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

Output

Each call returns the maximum K seen so far.

1   # [10,20)
1   # [50,60) — disjoint
2   # [10,40) overlaps [10,20)
3   # [5,15) lands on [10,15) where 2 events already overlap
3
3

Constraints

• 0 ≤ start < end ≤ 10⁹
• At most 400 calls to book.

Intuition

Keep a delta timeline — a map from time to change-in-active-count. For each booking, bump timeline[start] += 1 and timeline[end] -= 1. To answer, walk the map in time order and maintain a running sum; the peak is the answer.

Time:    5   10   15   20   40
Delta:  +1   +1   -1   -1   -1
Active:  1    2    1*  0   -1 → normalised to max 3 via sum
                   ↑ peak = 3 (actually sum pattern gives max 3 via +1+1+1-...)

Solution

from collections import defaultdict
 
class MyCalendarThree:
    def __init__(self):
        self.timeline = defaultdict(int)
 
    def book(self, start: int, end: int) -> int:
        self.timeline[start] += 1
        self.timeline[end] -= 1
 
        active = max_k = 0
        for t in sorted(self.timeline):
            active += self.timeline[t]
            max_k = max(max_k, active)
 
        return max_k

class MyCalendarThree {
    private timeline = new Map<number, number>();
 
    book(start: number, end: number): number {
        this.timeline.set(start, (this.timeline.get(start) ?? 0) + 1);
        this.timeline.set(end, (this.timeline.get(end) ?? 0) - 1);
 
        let active = 0, maxK = 0;
        const keys = [...this.timeline.keys()].sort((a, b) => a - b);
        for (const key of keys) {
            active += this.timeline.get(key)!;
            maxK = Math.max(maxK, active);
        }
 
        return maxK;
    }
}

Complexity

Edge Case Thinking