Python 0732.py
class MyCalendarThree:
def __init__(self):
self.changes = defaultdict(int)
def book(self, startTime: int, endTime: int) -> int:
self.changes[startTime] += 1
self.changes[endTime] -= 1
result = 0
current = 0
for c in sorted(self.changes):
current += self.changes[c]
result = max(result, current)
return result
Difficulty
and has an acceptance rate of about 72% (100k+ submissions).
Typical patterns to solve this problem:
- Binary Search
- Design
- Ordered Set
- Prefix Sum
- Segment Tree
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The MyCalendarThree class implements a sweep-line algorithm to track the maximum number of concurrent events after each booking. It stores incremental changes at event boundaries and recomputes the peak overlap whenever a new interval is added.
Initialization
The constructor creates a dictionary that automatically supplies a zero value for unseen keys. This dictionary, named changes, records how many events start or end at each timestamp.
class MyCalendarThree:
def __init__(self):
self.changes = defaultdict(int)
The use of defaultdict(int) eliminates the need for explicit existence checks before updating a count, keeping the code concise and ensuring constant-time insertion.
Booking an Interval
When book(startTime, endTime) is called, the method records two delta entries: a +1 at the start time and a -1 at the end time. These deltas represent the net change in the number of active events at the corresponding moments.
def book(self, startTime: int, endTime: int) -> int:
self.changes[startTime] += 1
self.changes[endTime] -= 1
By storing only the differences rather than every individual event, the structure remains compact even when many intervals overlap.
Computing the Maximum Overlap
After updating the delta map, the method iterates over the timestamps in sorted order, accumulating the running total of active events (current). The highest value observed during this sweep (result) is the answer to return.
result = 0
current = 0
for c in sorted(self.changes):
current += self.changes[c]
result = max(result, current)
return result
The sorted traversal guarantees that the sweep processes timestamps chronologically, correctly handling the order of starts and ends that share the same coordinate.
Edge Cases Handled
The implementation gracefully manages several boundary conditions:
-
Zero-length intervals (
startTime == endTime): Both a+1and a-1are recorded at the same key. During the sweep, the net change at that point is zero, leaving the overlap count unchanged, which matches the expectation that an instantaneous event does not increase concurrency. -
Negative timestamps: Since dictionary keys are plain integers, the algorithm works for any signed integer value, allowing bookings that start before a reference epoch.
-
Multiple events sharing a boundary: When several intervals start or end at the same timestamp, the accumulated delta at that key reflects the combined effect, and the sweep correctly updates the running total in a single step.
-
Repeated bookings of identical intervals: Each call adds another
+1and-1pair for the same boundaries, incrementally raising the overlap count as intended.
Performance Optimizations
The code leverages a few techniques that keep the runtime efficient for typical usage patterns:
-
Constant-time updates: Adding the start and end deltas uses direct dictionary indexing, which is O(1) on average.
-
Lazy aggregation: The sweep recomputes the maximum overlap only when a new booking arrives, avoiding the need for a separate data structure to maintain the current peak.
-
Built-in
max: Using the built-inmaxfunction to compare the running total with the current best avoids explicit conditional branches. -
Compact storage: By storing only the net change at each distinct timestamp, the memory footprint grows proportionally to the number of unique boundaries rather than the total number of intervals.
These choices make the class well-suited for scenarios where the number of distinct timestamps remains moderate relative to the total number of bookings.
ELI5 - Simplified Explanation
Imagine that the calendar is like a long sidewalk where different events want to claim a spot. This code uses a clever trick to keep track of how many people are using the same spot at the same time.
The computer keeps a little notebook called changes that notes down every time someone arrives and every time someone leaves. When an event starts at a specific time, the notebook adds a mark to that time slot to show one more person is there. When an event finishes, it takes a mark away because that person has gone home.
Whenever a new event is added, the computer takes out the notebook and lists all the times in order from the very beginning to the very end. It walks down the path starting with zero people and adds or subtracts the marks it finds in the notebook as it goes along. By checking the notebook at every step, the computer counts how many events are happening at the exact same moment. It keeps a record of the highest number it ever reaches during this walk, which tells everyone how many events are overlapping at the busiest part of the day.
Code Quality
Complexity Analysis
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| author | solutions | ||||||||
| www | AlgoMonster | C++ | Java | Python | TS | ||||
| WalkCCC | C++ | Java | Python | ||||||
| leetcode.ca | C++ | Java | Python | Go | TS | ||||
| LeetcodeHelp | C++ | Java | Python | ||||||
| MemoryLimitExceeded | C++ | Python | |||||||
| Progiez | C++ | Java | Python | ||||||
| github | black-shadows | C++ | |||||||
| charles-wangkai | Java | ||||||||
| everthis | JS | ||||||||
| halfrost | Go | ||||||||
| JoshCrozier | JS | ||||||||
| lkwq007 | Python | ||||||||
| qiyuangong | Python | ||||||||
| ruoru | Rust | ||||||||
| suxrobGM | C# | ||||||||
| varunu28 | Java | ||||||||
| vthwang | Java | ||||||||
| wisdompeak | C++ | ||||||||
| zfang399 | C++ | ||||||||
| AlgoMonster | C++, Python, Java, TypeScript | ||||||||
| WalkCCC | C++, Python, Java | ||||||||
| leetcode.ca | C++, Go, Java, Python, TypeScript | ||||||||
| LeetcodeHelp | C++, Java, Python | ||||||||
| MemoryLimitExceeded | Python, C++ | ||||||||
| Progiez | C++, Java, Python | ||||||||
| black-shadows | C++, C++ | ||||||||
| charles-wangkai | Java | ||||||||
| everthis | JavaScript | ||||||||
| halfrost | Go | ||||||||
| JoshCrozier | JavaScript | ||||||||
| lkwq007 | Python | ||||||||
| qiyuangong | Python | ||||||||
| ruoru | Rust | ||||||||
| suxrobGM | C# | ||||||||
| varunu28 | Java | ||||||||
| vthwang | Java | ||||||||
| wisdompeak | C++ | ||||||||
| zfang399 | C++ |
Videos
Similar Problems
- problem 729: My Calendar I
- problem 731: My Calendar II
- problem 2276: Count Integers in Intervals
Solved On The Same Day
- problem 2932: Maximum Strong Pair XOR I
- problem 731: My Calendar II
- problem 792: Number of Matching Subsequences
- problem 820: Short Encoding of Words
- problem 911: Online Election
- problem 950: Reveal Cards In Increasing Order
- problem 1023: Camelcase Matching
- problem 1038: Binary Search Tree to Greater Sum Tree
- problem 1170: Compare Strings by Frequency of the Smallest Character
- problem 1171: Remove Zero Sum Consecutive Nodes from Linked List
- problem 1696: Jump Game VI
- problem 2327: Number of People Aware of a Secret
- problem 432: All O`one Data Structure
- problem 1044: Longest Duplicate Substring
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality