Abstract / Summary

You must book events without allowing three overlapping events at any time.

Note

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

This problem is ranked as

and has an acceptance rate of about 63% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Design
• Ordered Set
• Prefix Sum
• Segment Tree

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.

Overview

The provided implementation defines a calendar that permits at most two overlapping events. It maintains a differential map of time points to efficiently track how many events are active at any moment. When a new booking is requested, the code temporarily applies the change, scans the timeline to detect a triple overlap, and, if necessary, rolls back the modification before reporting failure. The design leverages Python’s defaultdict for concise updates and short-circuit evaluation to avoid unnecessary work.

Initialization

def __init__(self):
    self.changes = defaultdict(int)

During object construction a defaultdict of integers is created. This structure stores the net change in the number of active events at each distinct time point. By default, any unseen key yields 0, allowing the code to increment or decrement counts without explicit existence checks.

Booking Process

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

When a booking request arrives, the method records a +1 at the start time and a -1 at the end time. This “difference array” approach means that the cumulative sum of the values, when traversed in chronological order, reflects the number of concurrent events at each interval. The update is performed before any validation, simplifying the later rollback logic.

Triple Booking Detection and Reversion

    current = 0
    for c in sorted(self.changes):
        current += self.changes[c]
        if current == 3:
            # undo booking
            self.changes[start] -= 1
            self.changes[end]   += 1
            return False
    return True

The method iterates over the sorted keys of the changes map, accumulating the net changes to compute the active event count (current). If the count ever reaches three, a triple booking would occur. At that moment the code reverses the earlier adjustments by subtracting the previously added +1 at start and adding back the -1 at end. The method then returns False to indicate that the booking cannot be accommodated. If the loop completes without encountering a triple overlap, the temporary changes are confirmed and the method returns True.

Edge Cases Handled

The algorithm gracefully handles bookings that start and end at the same timestamp. In such a case the +1 and -1 are applied to the identical key, resulting in a net zero change; the cumulative count remains unaffected, and the booking is effectively a no-op that never triggers a triple overlap. Overlapping intervals of arbitrary length are managed because the cumulative sum reflects the exact number of active events across all sub-intervals. The rollback mechanism ensures that even if a triple overlap is detected partway through the scan, the internal state is restored to its pre-booking condition, preserving correctness for subsequent operations.

Performance Optimizations

The use of a differential map eliminates the need to store each individual interval, reducing memory overhead. Incremental updates (+= 1 and -= 1) are constant-time operations thanks to the underlying hash table. Sorting the keys on each booking incurs a cost proportional to the number of distinct time points, but the early exit when a triple overlap is found prevents scanning the entire timeline in many cases. By performing the rollback only when a conflict is detected, the implementation avoids unnecessary writes for successful bookings. The overall structure keeps the hot path-checking for a conflict-tight and focused on simple arithmetic and dictionary lookups.

Imagine you have a big wall calendar for your play dates. This code acts like a helper who keeps track of how many things are happening at the same time.

When you want to schedule a new time slot, the helper puts a little mark at the start time and another mark at the end time. These marks tell the helper that one more activity has started or finished.

After adding the new time, the helper looks at the entire calendar from the very beginning to the end. The helper walks through every single mark one by one and counts up how many activities are happening at that moment. If the helper ever sees that three activities are trying to happen at the exact same time, the helper knows the calendar is too crowded. In that case, the helper quickly takes away the marks added for the new activity so the calendar stays as it was before.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

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
	leetcode.ca	C++	Java	JS			Python		Go	TS
	LeetcodeHelp	C++	Java				Python
	MemoryLimitExceeded	C++					Python
	Progiez	C++	Java				Python
github	black-shadows	C++
	charles-wangkai		Java
	everthis			JS
	fpdjsns	C++
	gouthampradhan		Java
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007						Python
	martianoff				Scala
	ruoru					Rust
	suxrobGM							C#
	varunu28		Java
	wisdompeak	C++
	withaarzoo	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fpdjsns	C++
gouthampradhan	Java
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
martianoff	Scala
ruoru	Rust
suxrobGM	C#
varunu28	Java
wisdompeak	C++
withaarzoo	C++
zfang399	C++

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