097. Calendar Maximum Overlap

Why this mechanism works

Accumulate net changes at boundary times. After each insertion, sweep the sorted boundary map to recompute peak occupancy. Grouping equal timestamps into one delta naturally handles simultaneous endings and starts. This straightforward dynamic reference favors inspectable state over an advanced augmented-tree implementation.

State and boundaries

changes[time] is the net start-minus-end delta of all bookings. A sweep integrates those deltas into overlap counts.

Protocol

1. Increment the start delta and decrement the end delta.
2. Visit boundary times in sorted order.
3. Integrate active overlap and track its maximum.
4. Return the new maximum.

Visualization

book [10,20): changes +1 at 10, -1 at 20
book [15,25): add +1 at 15, -1 at 25
integrated peak between 15 and 20 is 2

Python implementation

from structures import run_operations

class OverlapCalendar:
    def __init__(self):
        self.changes = {}

    def book(self, start, end):
        self.changes[start] = self.changes.get(start, 0) + 1
        self.changes[end] = self.changes.get(end, 0) - 1
        active = peak = 0
        for time in sorted(self.changes):
            active += self.changes[time]
            peak = max(peak, active)
        return peak

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L5 __init__: self.changes = {}
self=OverlapCalendar{'changes':{}}

L8 book: self.changes[start] = self.changes.get(start, 0) + 1
self=OverlapCalendar{'changes':{...:...}}; start=10; end=20

L9 book: self.changes[end] = self.changes.get(end, 0) - 1
self=OverlapCalendar{'changes':{...:..., ...:...}}; start=10; end=20

L10 book: active = peak = 0
self=OverlapCalendar{'changes':{...:..., ...:...}}; start=10; end=20; active=0; peak=0

L11 book: for time in sorted(self.changes):
self=OverlapCalendar{'changes':{...:..., ...:...}}; start=10; end=20; active=0; peak=0; time=10

L12 book: active += self.changes[time]
self=OverlapCalendar{'changes':{...:..., ...:...}}; start=10; end=20; active=1; peak=0; time=10

L13 book: peak = max(peak, active)
self=OverlapCalendar{'changes':{...:..., ...:...}}; start=10; end=20; active=1; peak=1; time=10

L11 book: for time in sorted(self.changes):
self=OverlapCalendar{'changes':{...:..., ...:...}}; start=10; end=20; active=1; peak=1; time=20

... 24 intermediate state changes omitted ...

L11 book: for time in sorted(self.changes):
self=OverlapCalendar{'changes':{...:..., ...:..., ...:..., ...:..., ...:...}}; start=20; end=30; active=2; peak=2; time=25

L12 book: active += self.changes[time]
self=OverlapCalendar{'changes':{...:..., ...:..., ...:..., ...:..., ...:...}}; start=20; end=30; active=1; peak=2; time=25

L11 book: for time in sorted(self.changes):
self=OverlapCalendar{'changes':{...:..., ...:..., ...:..., ...:..., ...:...}}; start=20; end=30; active=1; peak=2; time=30

L12 book: active += self.changes[time]
self=OverlapCalendar{'changes':{...:..., ...:..., ...:..., ...:..., ...:...}}; start=20; end=30; active=0; peak=2; time=30

L5 __init__: self.changes = {}
self=OverlapCalendar{'changes':{}}

L8 book: self.changes[start] = self.changes.get(start, 0) + 1
self=OverlapCalendar{'changes':{...:...}}; start=1; end=3

L9 book: self.changes[end] = self.changes.get(end, 0) - 1
self=OverlapCalendar{'changes':{...:..., ...:...}}; start=1; end=3

L10 book: active = peak = 0
self=OverlapCalendar{'changes':{...:..., ...:...}}; start=1; end=3; active=0; peak=0

L11 book: for time in sorted(self.changes):
self=OverlapCalendar{'changes':{...:..., ...:...}}; start=1; end=3; active=0; peak=0; time=1

L12 book: active += self.changes[time]
self=OverlapCalendar{'changes':{...:..., ...:...}}; start=1; end=3; active=1; peak=0; time=1

L13 book: peak = max(peak, active)
self=OverlapCalendar{'changes':{...:..., ...:...}}; start=1; end=3; active=1; peak=1; time=1

L11 book: for time in sorted(self.changes):
self=OverlapCalendar{'changes':{...:..., ...:...}}; start=1; end=3; active=1; peak=1; time=3

... 4 intermediate state changes omitted ...

L12 book: active += self.changes[time]
self=OverlapCalendar{'changes':{...:..., ...:...}}; start=1; end=3; active=2; peak=0; time=1

L13 book: peak = max(peak, active)
self=OverlapCalendar{'changes':{...:..., ...:...}}; start=1; end=3; active=2; peak=2; time=1

L11 book: for time in sorted(self.changes):
self=OverlapCalendar{'changes':{...:..., ...:...}}; start=1; end=3; active=2; peak=2; time=3

L12 book: active += self.changes[time]
self=OverlapCalendar{'changes':{...:..., ...:...}}; start=1; end=3; active=0; peak=2; time=3

Why the solution is correct

Each stored interval contributes one exactly on its half-open duration. Summed deltas therefore reconstruct the full occupancy function after every insertion. Its maximum over boundary segments is the correct calendar-wide peak.

Time and space

O(b log b) time for the bth booking and O(b) state; O(B^2 log B) total upper bound over B bookings. An augmented ordered tree can improve updates.

Common mistakes

Reporting only overlap with the newest interval is not the requested global maximum. Claiming logarithmic updates for a full resweep is incorrect.

Reasoning card

Transfer exercise

Design a tree node summary containing subtree delta sum and maximum prefix sum; derive how two child summaries combine.