Problem 732

Abstract / Summary

You must book events without overlaps by checking if any new event overlaps with existing ones within a certain time limit.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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
15 lines | 420 bytes | submitted November 23, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

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
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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 +1 and a -1 are 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 +1 and -1 pair 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-in max function 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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 7 | μ = 7.04 | σ = 1.40

Complexity Analysis

not analyzed yet

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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++
33 links | 19 authors | 8 languages

Videos

10 videos   did my crawler come up with invalid videos ? drop me a line.

Similar Problems

3 similar problems

Solved On The Same Day

15 solutions   November 23, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • 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