My Calendar III: Maximum K-Booking with Sweep Line

My Calendar III (LeetCode #732) asks you to build a booking system where, after every new event, you report the maximum number of overlapping events across the entire calendar. This is the hardest of the three My Calendar problems, and the key insight is a technique called the sweep line (or difference array) that lets you answer "what is the maximum overlap?" efficiently after every booking.

The problem

Design a MyCalendarThree class with a single method:

• book(start, end) adds a new event covering the half-open interval [start, end). Return the maximum k-booking after this call, where a k-booking means k events overlap at some point in time.

There is no restriction on double or triple bookings. You accept every event and simply report the worst-case overlap count.

Example:

• book(10, 20) returns 1 (one event, max overlap is 1)
• book(50, 60) returns 1 (two events, but they do not overlap)
• book(10, 40) returns 2 (overlaps with the first event between 10 and 20)
• book(5, 15) returns 3 (three events overlap between 10 and 15)
• book(5, 10) returns 3 (peak overlap is still 3, between 10 and 15)
• book(25, 55) returns 3 (peak overlap remains 3)

Why brute force fails

The naive approach would be to store every interval and, after each booking, check every pair of intervals to figure out the maximum overlap. With n bookings so far, that is O(n^2) per call. Over n total calls, the total work is O(n^3). For n = 400 (the problem constraint), that might pass, but the approach does not scale and misses the elegant structure of the problem.

You could also try painting each time unit as "occupied" on a timeline array, but the time values can be up to 10^9, so you cannot allocate an array that large.

The key insight

Instead of tracking full intervals, record just the boundary changes. For every event [start, end):

• Add +1 at time start (an event begins)
• Add -1 at time end (an event ends)

Store these deltas in a sorted map (ordered by time). After each booking, sweep through the sorted keys in order, accumulating a running sum. The running sum at any key tells you how many events are active at that moment. The maximum running sum across all keys is your answer.

This is the difference array technique applied to a sparse timeline. You never need to enumerate every time unit. You only process the boundary points where the overlap count changes.

The solution

from sortedcontainers import SortedDict

class MyCalendarThree:
    def __init__(self):
        self.diff = SortedDict()

    def book(self, start: int, end: int) -> int:
        self.diff[start] = self.diff.get(start, 0) + 1
        self.diff[end] = self.diff.get(end, 0) - 1

        max_k = 0
        running = 0
        for val in self.diff.values():
            running += val
            max_k = max(max_k, running)
        return max_k

If you do not want to use SortedDict (which keeps keys sorted automatically), you can use a plain defaultdict and sort the keys each time:

from collections import defaultdict

class MyCalendarThree:
    def __init__(self):
        self.diff = defaultdict(int)

    def book(self, start: int, end: int) -> int:
        self.diff[start] += 1
        self.diff[end] -= 1

        max_k = 0
        running = 0
        for key in sorted(self.diff):
            running += self.diff[key]
            max_k = max(max_k, running)
        return max_k

The SortedDict version is O(n log n) total over n calls (O(log n) insertion, O(n) sweep per call). The defaultdict version is O(n log n) per call due to sorting, but both comfortably pass the constraints.

Step-by-step walkthrough

Let us trace through each booking and see how the difference map evolves, and how sweeping through the sorted keys yields the maximum overlap count.

1book(10, 20)returns 1

2book(50, 60)returns 1

3book(10, 40)returns 2

4book(5, 15)returns 3

5book(5, 10)returns 3

6book(25, 55)returns 3

After book(5, 15) the diff map has keys [5, 10, 15, 20, 40, 50, 60]. Sweeping: at 5 the running sum hits 1, at 10 it jumps to 3 (that is the peak), then it drops as events end. The maximum is 3, and it stays at 3 for the remaining calls.

Complexity analysis

In both cases, n is the number of bookings made so far. Each book call must sweep through all boundary keys to find the maximum, which is O(n). The SortedDict version avoids re-sorting by maintaining order on insertion (O(log n) per insert), while the defaultdict version sorts all keys each time (O(n log n)).

For the given constraints (at most 400 calls), both approaches run well within time limits.

The building blocks

Sweep line / difference array

The core technique here is the sweep line: instead of tracking full intervals, you record boundary deltas and sweep through them in order.

This same idea powers:

• Meeting Rooms II (count maximum overlapping meetings)
• Car Pooling (track passengers at pickup/dropoff points)
• My Calendar I and II (detect double/triple bookings)
• Range addition problems (apply increments to ranges, then scan for final values)

The pattern is always the same: mark +1 at the start, -1 at the end, sort, and sweep. The running sum tells you the active count at any moment. If your brute force involves checking every pair of intervals, the sweep line almost certainly gives you a cleaner solution.

Edge cases

Single event. book(10, 20) on an empty calendar returns 1. The diff map has {10: 1, 20: -1}, and the sweep finds max = 1.

Non-overlapping events. Events like [10, 20) and [30, 40) never share a time point, so the max remains 1 after both bookings.

Events touching at endpoints. [10, 20) and [20, 30) do not overlap because the first event ends at 20 and the second starts at 20. The half-open interval convention ensures no double counting at the boundary.

Identical events. Booking [10, 20) three times produces diff = {10: 3, 20: -3}. The sweep finds max = 3. Each duplicate adds to the overlap.

Large time values. Start and end can be up to 10^9, but you only store boundary points (at most 2n entries for n bookings), so memory is never an issue.

From understanding to recall

The code is short, but the reasoning behind it is what matters. You need to internalize the three-step pattern: (1) record +1 at start and -1 at end, (2) iterate through sorted keys accumulating a running sum, (3) track the maximum running sum.

Practice by writing the solution from scratch without looking at any reference. Then do it again in a few days. After a few repetitions, the sweep line becomes second nature, and you will recognize it instantly in any "maximum overlap" problem.

Related posts

• My Calendar I - The single-booking version where you must prevent double bookings
• My Calendar II - Allow double bookings but prevent triple bookings
• Meeting Rooms II - Find the minimum number of conference rooms using the same sweep line idea