My Calendar III

My Calendar III

What is this problem about?

The My Calendar III problem asks you to design a calendar where the book(start, end) method always succeeds (no rejections) but returns the maximum number of overlapping bookings after each booking. This My Calendar III coding problem requires efficiently tracking the maximum concurrent events at any point in time as events are added dynamically.

Why is this asked in interviews?

Amazon, Google, and Bloomberg ask this hard-level extension because it requires an efficient data structure for "maximum overlap at any point" — a sweep-line problem. The design, binary search, ordered set, segment tree, and prefix sum interview pattern is comprehensively tested. It directly applies to conference room booking, bandwidth allocation, and scheduling systems.

Algorithmic pattern used

Difference array with sorted map (or segment tree). For each book(start, end): increment the count at start by +1 and decrement at end by -1 in a sorted map. To find the maximum overlap after each booking, scan the difference map in sorted key order, accumulating the running sum, and track the maximum.

Example explanation

Book (10, 20): diff={10:+1, 20:-1}. Scan: at 10 → sum=1. Max = 1. Book (50, 60): diff={10:+1, 20:-1, 50:+1, 60:-1}. Scan: max = 1 (two separate events). Book (10, 40): diff={10:+2, 20:-1, 40:-1, 50:+1, 60:-1}. Scan: at 10→2, at 20→1. Max = 2. Book (5, 15): diff={5:+1, 10:+2, 15:-1, 20:-1, 40:-1, 50:+1, 60:-1}. At 5→1, 10→3. Max = 3.

Common mistakes candidates make

• Rescanning the entire difference map from scratch each time (O(n) per query, which is acceptable but can be optimized).
• Not using a sorted map — unsorted keys give wrong sweep order.
• Confusing half-open intervals: end gets -1, not end-1.
• Forgetting to return the current maximum after each booking.

Interview preparation tip

The difference array technique — +1 at start, -1 at end, then prefix sum to get overlaps at each point — is the foundational tool for maximum-overlap problems. For dynamic insertion (as in this calendar problem), a sorted map (TreeMap in Java, SortedDict in Python) maintains the difference array efficiently. After mastering My Calendar I, II, and III, you'll have a complete toolkit for interval management problems: overlap detection, k-level booking, and maximum concurrent count.