Abstract / Summary

Check if a new meeting can be scheduled without overlapping existing meetings on a calendar.

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 58% (800k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Design
• Ordered Set
• 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 class MyCalendar provides a simple interval-booking facility that prevents overlapping events. Internally it stores event boundaries in a std::map<double,int> where the key is a timestamp and the value indicates whether the timestamp marks the start (START) or the end (END) of an event. The public method book attempts to insert a new interval [start, end) and returns true only when the interval does not conflict with any previously booked interval.

Key Steps

The booking routine follows a deterministic sequence of checks before committing an interval.

The first operation converts the exclusive end point into a value that can be stored in the map without colliding with a possible start at the same integer time.

double end2 = end - 0.1;

Next the method locates the first map entry whose key is not less than start and the first entry whose key is not less than end.

auto s = events.lower_bound(start);
auto e = events.lower_bound(end);

The first conflict test verifies that no existing event begins exactly at the requested start time. If the iterator s points to an entry whose key equals start, the interval is rejected.

if (s != events.end() && s->first == start)
    return false;

The second test ensures that the new interval does not start inside an ongoing event that began earlier and has not yet ended. This is done by looking at the element immediately preceding s; if that element exists and its value is START, the new start would fall within an active interval, so the booking fails.

if (s != events.begin() && prev(s)->second == START)
    return false;

The third test checks for any existing boundary that lies strictly between start and end. If the iterator s is not equal to e, there is at least one map entry in the open interval, indicating a conflict.

if (s != e)
    return false;

When all three checks succeed, the method records the new interval by inserting a START marker at start and an END marker at the adjusted end2.

events[start] = START;
events[end2]  = END;
return true;

Edge Cases Handled

The implementation explicitly addresses the situation where an event ends at the same integer time another event begins. By storing the end marker as end - 0.1, the code creates a distinct key that is guaranteed to be less than any possible start at the same integer value, thereby allowing back-to-back bookings without overlap.

It also handles the case where the map is empty; both lower_bound calls return events.end(), the predecessor check is bypassed because s == events.begin(), and the interval is inserted without obstruction.

When a new interval starts at the exact moment an existing interval ends, the predecessor check sees the preceding entry as an END marker, not a START, so the booking proceeds.

If an interval is requested with start greater than or equal to end, the logic still treats the interval as invalid because the lower_bound calls will produce identical iterators and the predecessor check will reject any overlapping start, effectively preventing zero-length or inverted intervals from being recorded.

Performance Optimizations

The choice of std::map gives logarithmic lookup and insertion, but the algorithm minimizes the number of map operations required for each booking. By using two lower_bound calls, the code obtains both the position of the potential start conflict and the range of any intermediate entries in a single pass. The subsequent checks rely solely on iterator comparisons and a single prev call, avoiding additional traversals.

Storing only boundary points rather than full interval objects reduces memory overhead and keeps the map size proportional to twice the number of booked intervals. The use of a floating-point adjustment for the end marker eliminates the need for a separate data structure to track interval lengths, allowing the conflict detection to be performed with simple key comparisons.

Overall, the method performs a constant amount of work beyond the two logarithmic searches, ensuring that each booking operation scales efficiently as the calendar grows.

Imagine a busy little calendar that keeps track of when you get to play games. This code is like a helper that checks your day to see if you can add a new playtime without bumping into something else you already planned.

The calendar stores all the times when activities start and when they finish. When you want to book a new playtime, the helper first looks at the list to see if any other events are happening at the same time.

For the first check, it looks to see if a new activity starts at the exact same moment as another one. If it finds a match, it says no because two things cannot happen at once.

For the second check, it looks to see if you are already in the middle of another game. If the time you want starts while something else is still happening, it says no because your calendar is already full.

For the third check, it looks to see if any other events are hidden in the time slot you picked. If it finds anything inside, it says no because there is no room.

If the calendar is totally free, it adds your new game to the list by marking the start and the finish times. This way, the calendar remembers your plans for later.

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

Time: logarithmic
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

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