Module 5 · Advanced Intervals

My Calendar II

MediumProblem 11 of 12 10 min read ~30 min to solve LeetCode

IntervalsDesignTreeMapSweep LinePrefix Sum

Asked atGoogleAmazonMicrosoftMetaOracle

Problem Statement

Design a MyCalendarTwo data structure. book(startTime, endTime) adds an event on the half-open interval [startTime,endTime) if doing so does not create any time point covered by three events. Double bookings are allowed. Triple bookings are not.

Input

A constructor call MyCalendarTwo() 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 without creating a triple booking.

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 contribute at time x

Examples

Example 1

Input:

operations = [MyCalendarTwo, book, book, book, book, book, book], arguments = [[], [10,20], [50,60], [10,40], [5,15], [5,10], [25,55]]

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

Explanation: [5,15) would make [10,15) covered by three events: [10,20), [10,40), and [5,15). The later [25,55) is accepted because it never pushes overlap depth above two.

Example 2

Input:

operations = [MyCalendarTwo, book, book, book, book], arguments = [[], [1,5], [5,10], [2,6], [4,7]]

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

Explanation: [1,5) and [5,10) only touch. Adding [2,6) creates double-covered regions, but adding [4,7) would make [4,5) and [5,6) triple-covered.

Learning Objectives

Represent interval coverage changes with boundary deltas rather than storing every point.
Use a **TreeMap** sweep line to compute active booking depth in time order.
Rollback tentative mutations when a booking violates the maximum allowed overlap.
Distinguish double booking from triple booking using prefix sums over event boundaries.

Intuition

Pattern Recognition

The phrase allow double booking but reject triple booking changes the problem from finding one conflicting neighbour to measuring overlap depth. A single predecessor check is no longer enough: a new event may overlap different existing events in different subranges, and the dangerous point is where active count becomes three.

The sweep-line pattern treats each interval as two boundary events: +1 at its start and -1 at its end. If boundaries are processed in sorted time order, the running prefix sum is the number of active bookings after that boundary. A tentative booking is valid exactly when every prefix sum remains at most two.

Common mistakes

×Rejecting any overlap, which solves My Calendar I but not the double-booking variant.
×Checking only the new interval's endpoints instead of every boundary where active count can change.
×Forgetting to rollback both boundary deltas after detecting a triple booking.
×Treating an end boundary as still active at the same time another event starts.

Algorithm Explanation

Key idea

Use a TreeMap named delta where each key is a time and each value is the net active-count change at that time. To try book(startTime,endTime), add +1 at startTime and -1 at endTime, then sweep the values in sorted key order. If the active count ever exceeds two, undo the two delta changes and reject. Otherwise keep the changes.

Interval walkthrough

Accept book([10,20]) by storing deltas 10:+1, 20:-1. Accept book([10,40]) by updating to 10:+2, 20:-1, 40:-1; the sweep reaches active count two on [10,20) and one on [20,40). Now try book([5,15]). Tentative deltas become 5:+1, 10:+2, 15:-1, 20:-1, 40:-1. Sweeping gives active one after time 5, then active three after time 10, so [10,15) would be triple-booked. Roll back 5:+1 and 15:-1, leaving the previous valid map unchanged.

Algorithm

Store boundary changes in a sorted TreeMap from time to net delta.
For each book, tentatively add +1 at startTime and -1 at endTime.
Sweep delta.values() in key order while maintaining active.
If active > 2, undo the tentative start and end changes and return false.
If the sweep completes, keep the changes and return true.
Remove a boundary key whenever its net delta becomes zero so the map stays compact.

Solutions

Solution: TreeMap boundary-count sweep

When to prefer this:

Use this when the maximum allowed overlap is small and the number of calls is modest, but the time range is too large for an array of points.

Each booking contributes a start delta and an end delta. The sorted TreeMap lets the implementation replay the sweep line after a tentative update. If any prefix sum reaches three, the update is invalid and is rolled back immediately.

Step-by-step

Maintain delta, a TreeMap from boundary time to net active-count change.
On book(startTime,endTime), add +1 at the start and -1 at the end.
Walk the deltas in increasing time order, accumulating the active booking count.
If the count exceeds two, apply the inverse changes to rollback the tentative booking.
Return false after rollback, or true if every prefix sum stayed at most two.

Time

O(n) per book, with O(log n) TreeMap updates

Space

O(n)

n is the number of stored boundary times. The tentative add and rollback are logarithmic; validating overlap depth requires sweeping the ordered boundaries.

Java implementation

Loading…

Dry Run

Sample input

Sequence of calls: book([10,20]), book([10,40]), book([5,15]), book([20,30]). The map stores boundary deltas.

call	tentative delta map	maximum active count	result
book([10,20])	{10:+1, 20:-1}	1	true
book([10,40])	{10:+2, 20:-1, 40:-1}	2	true
book([5,15])	{5:+1, 10:+2, 15:-1, 20:-1, 40:-1}	3 on [10,15), rollback	false
book([20,30])	{10:+2, 30:-1, 40:-1}	2	true

The rejected call never remains in the map. The accepted book([20,30]) starts exactly when [10,20) ends, so the combined delta at time 20 cancels out and does not create a triple booking.

Interview Tips

Frame the solution as a sweep line over boundary events, not as checking individual times. The active count only changes at starts and ends, so those are the only positions that need validation. Be explicit about rollback: a design method must leave the object exactly as it was when the operation returns false.

Likely follow-ups

How would you generalize this design to reject overlap depth greater than **k**?
How would you optimize booking validation for a much larger number of calls?
How would you return the first triple-booked interval instead of **false**?
How would cancellation change the boundary-count representation?

Key Takeaways

Double booking is allowed, so the question is overlap depth, not existence of overlap.
Boundary deltas compress huge time ranges into the only times where active count changes.
A tentative mutation plus rollback is a clean design pattern for validating state changes.
Half-open endpoints are handled naturally by adding **-1** at the end boundary.

Reusable template: Boundary-count sweep: record start and end deltas in sorted order, scan prefix sums to validate overlap depth, and rollback failed tentative updates.