Skip to main content

732 - My Calendar III

Difficulty: Hard | Pattern: Segment Tree / Difference Array | Company tags: Google, Amazon

Problem Statement​

A k-booking happens when k events have some non-empty intersection (i.e., there is some time that is common to all k events.)

Implement the MyCalendarThree class:

  • MyCalendarThree() Initializes the object.
  • int book(int startTime, int endTime) Returns an integer k representing the largest integer such that there exists a k-booking in the calendar.

Example:

MyCalendarThree cal = new MyCalendarThree();
cal.book(10, 20) → 1
cal.book(50, 60) → 1
cal.book(10, 40) → 2
cal.book(5, 15)  → 3

Approach: Difference Array + SortedDict — O(n log n)​

Key insight: Use a difference array: at each booking's start, increment by 1; at end, decrement by 1. The running sum at any point is the current booking count. Track sorted endpoints and compute max prefix sum.

from sortedcontainers import SortedDict

class MyCalendarThree:
    def __init__(self):
        self.diff = SortedDict()
    
    def book(self, startTime: int, endTime: int) -> int:
        self.diff[startTime] = self.diff.get(startTime, 0) + 1
        self.diff[endTime] = self.diff.get(endTime, 0) - 1
        
        max_k = 0
        cur = 0
        for delta in self.diff.values():
            cur += delta
            max_k = max(max_k, cur)
        
        return max_k

Dry Run​

After book(10,20): diff keys 10→+1, 20→-1; scan: cur=1 → max=1 After book(10,40): diff keys 10→+2, 20→-1, 40→-1; scan: 2,1,0 → max=2 After book(5,15): diff keys 5→+1, 10→+2, 15→-1, 20→-1, 40→-1; scan: 1,3,2,1,0 → max=3 ✓

Complexity​

  • Time: O(n) per booking (scan all events)
  • Space: O(n) — one entry per unique endpoint