Module 5 · Advanced Intervals

My Calendar I

MediumProblem 10 of 12 9 min read ~25 min to solve LeetCode

IntervalsDesignTreeMapBinary Search TreeCalendar

Asked atGoogleAmazonMicrosoftMetaBloomberg

Problem Statement

Design a MyCalendar data structure. book(startTime, endTime) tries to add an event on the half-open interval [startTime,endTime). The booking succeeds only if it does not overlap any existing event. Return true when the event is stored, otherwise return false and leave the calendar unchanged.

Input

A constructor call MyCalendar() followed by a sequence of book(startTime, endTime) calls.

Output

For the constructor output null. For each book call, output whether the event was accepted into the calendar.

Constraints

•0 <= startTime < endTime <= 10^9
•At most 1000 calls will be made to book
•Intervals are half-open, so an event ending at time x does not overlap an event starting at time x

Examples

Example 1

Input:

operations = [MyCalendar, book, book, book], arguments = [[], [10,20], [15,25], [20,30]]

Output: [null, true, false, true]

Explanation: The first event is stored. The second overlaps [10,20), so it is rejected. The third starts exactly when [10,20) ends, so the half-open intervals do not overlap.

Example 2

Input:

operations = [MyCalendar, book, book, book, book], arguments = [[], [5,10], [10,15], [7,8], [1,5]]

Output: [null, true, true, false, true]

Explanation: [5,10) and [10,15) touch but do not overlap. [7,8) falls inside [5,10), while [1,5) ends exactly before the first event begins.

Learning Objectives

Model calendar events as half-open intervals and apply the correct overlap test.
Use **TreeMap** ordering to inspect only the closest previous and next events.
Explain why non-neighbour intervals cannot be the first conflict in a start-sorted calendar.
Preserve the calendar state when a booking is rejected.

Intuition

Pattern Recognition

The design signal is an online interval set: events arrive one at a time, and each accepted event must remain sorted for future checks. Sorting the full calendar after every call is unnecessary. A list scan works for small limits, but it does not teach the scalable interview pattern.

Use a TreeMap keyed by event start time. For a new interval [startTime,endTime), only two neighbours can create the first conflict: the event with the greatest start not exceeding startTime, and the event with the smallest start not less than startTime. If the previous event ends after startTime, it overlaps from the left. If the next event starts before endTime, it overlaps from the right.

Common mistakes

×Treating intervals as closed and rejecting back-to-back events like **[10,20)** and **[20,30)**.
×Scanning all events even though the start-sorted predecessor and successor are sufficient.
×Checking only the previous event and missing a next event that starts inside the new interval.
×Adding the event before validation, then forgetting to remove it on failure.

Algorithm Explanation

Key idea

Store accepted events in a TreeMap where the key is the start time and the value is the end time. In start order, any event before the predecessor ends no later than the predecessor, and any event after the successor starts no earlier than the successor. Therefore the booking decision only needs floorKey(startTime) and ceilingKey(startTime).

Interval walkthrough

Begin with an empty calendar. After book([10,20]), store {10 -> 20}, representing [10,20). For book([15,25]), the floor neighbour is [10,20), and 20 > 15, so the new event enters the existing event and must be rejected. The calendar stays {10 -> 20}. For book([20,30]), the floor neighbour is still [10,20), but 20 > 20 is false, and there is no ceiling neighbour. The new event is accepted, giving {10 -> 20, 20 -> 30}.

Algorithm

Create a TreeMap named events from start time to end time.
For book(startTime, endTime), find previousStart = events.floorKey(startTime).
If previousStart exists and events.get(previousStart) > startTime, return false.
Find nextStart = events.ceilingKey(startTime).
If nextStart exists and nextStart < endTime, return false.
Insert startTime -> endTime and return true.

Solutions

Solution: TreeMap neighbour check

When to prefer this:

Use this when events are inserted online and each booking only needs to know whether it overlaps an already accepted interval.

The TreeMap keeps events sorted by start time. A candidate can only overlap the immediate predecessor or immediate successor in that sorted order, so book performs two logarithmic neighbour lookups and inserts only after both checks pass.

Step-by-step

Store each accepted event as start -> end in the TreeMap.
Use floorKey(startTime) to find the closest event that starts before or at the candidate.
Reject if that event's end is greater than startTime.
Use ceilingKey(startTime) to find the closest event that starts after or at the candidate.
Reject if that start is less than endTime.
If neither neighbour overlaps, insert the event and return true.

Time

O(log n) per book

Space

O(n)

**TreeMap** predecessor, successor, and insert operations are logarithmic in the number of accepted events.

Java implementation

Loading…

Dry Run

Sample input

Sequence of calls: book([10,20]), book([15,25]), book([20,30]), book([5,10]). The calendar stores start -> end pairs.

call	TreeMap before	neighbour decision	result
book([10,20])	{}	no floor or ceiling conflict, store 10 -> 20	true
book([15,25])	{10 -> 20}	floor [10,20) ends after 15, reject	false
book([20,30])	{10 -> 20}	floor [10,20) ends at 20, no overlap	true
book([5,10])	{10 -> 20, 20 -> 30}	ceiling [10,20) starts at 10, no overlap	true

The important boundary is strict: an existing end equal to the new start is safe, and a next start equal to the new end is safe. Only end > startTime or nextStart < endTime creates a double booking.

Interview Tips

Say half-open intervals out loud before writing comparisons. Then justify why only two neighbours matter in a start-sorted map. A strong explanation is that every earlier interval starts no later than the floor interval, and because accepted intervals never overlap, it must also end no later than the floor interval. Symmetrically, every later interval starts no earlier than the ceiling interval.

Likely follow-ups

How would you support cancelling an event while keeping the same complexity?
How would the checks change if intervals were closed instead of half-open?
How would you return the conflicting interval rather than just **false**?
How would you extend the design to allow double bookings but reject triple bookings?

Key Takeaways

Half-open intervals allow endpoints to touch without overlap.
A start-sorted **TreeMap** reduces booking validation to predecessor and successor checks.
Rejected bookings must not mutate the calendar.
The reusable pattern is ordered interval set plus neighbour queries.

Reusable template: Ordered interval set: store disjoint intervals by start, inspect the closest left and right neighbours, and mutate only when both boundaries are safe.