LeetCode 732 - My Calendar III
This problem asks us to design a calendar system that supports adding time intervals and reporting the highest number of overlapping events seen so far. Each booking is represented as a half open interval [startTime, endTime).
Difficulty: 🔴 Hard
Topics: Binary Search, Design, Segment Tree, Prefix Sum, Ordered Set
Solution
Problem Understanding
This problem asks us to design a calendar system that supports adding time intervals and reporting the highest number of overlapping events seen so far.
Each booking is represented as a half open interval [startTime, endTime). This means the event includes startTime but excludes endTime. Two events overlap only if they share some non empty time range. For example:
[10, 20)and[15, 25)overlap from15to20[10, 20)and[20, 30)do not overlap because20is excluded from the first interval
After every booking operation, we must return the maximum number of simultaneous overlapping events anywhere in the calendar.
The phrase k-booking means there exists at least one moment where exactly k events overlap. Our goal is to continuously track the largest such value.
The constraints are important:
0 <= startTime < endTime <= 10^9- At most
400bookings
The time range is extremely large, so we cannot build an array indexed by time. However, the number of bookings is relatively small, which suggests that algorithms based on processing interval boundaries are practical.
A naive implementation might try checking overlap counts for every unit of time, but the coordinate range is too large. Another naive approach might compare every interval against every other interval repeatedly, which becomes inefficient as bookings grow.
Important edge cases include:
- Intervals that only touch at endpoints, such as
[10, 20)and[20, 30), which are not overlapping - Many fully overlapping intervals
- Nested intervals
- Sparse intervals spread across very large timestamps
- Repeated bookings with identical ranges
The problem guarantees valid intervals because startTime < endTime.
Approaches
Brute Force Approach
A straightforward solution is to store all intervals and, after each booking, recompute the maximum overlap from scratch.
One way to do this is:
- Collect all interval boundaries
- For every unique time segment, count how many intervals cover it
- Track the maximum overlap count
Another brute force variation is to discretize all endpoints and scan through overlaps manually.
This works because overlap counting is fundamentally determined by interval start and end boundaries. However, recomputing overlaps from scratch after every booking becomes inefficient.
If there are n bookings, each insertion may require scanning all intervals and all endpoints again, leading to roughly O(n^2) or worse overall complexity.
Optimal Approach, Sweep Line with Difference Map
The key insight is that interval overlaps can be represented using a difference array idea.
For every booking [start, end):
- Add
+1atstart - Add
-1atend
When we process times in sorted order and maintain a running prefix sum:
- The prefix sum represents the number of active intervals at that moment
- The maximum prefix sum is the answer
This technique is often called a sweep line algorithm.
Instead of explicitly tracking every interval overlap, we only track changes at boundaries. Since there are at most 400 bookings, the total number of boundary points is at most 800, making sorting and scanning efficient.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) per booking | O(n) | Recomputes overlaps repeatedly |
| Optimal | O(n log n) per booking | O(n) | Uses sweep line with ordered boundary changes |
Algorithm Walkthrough
Optimal Algorithm, Sweep Line with Difference Map
- Initialize a map called
timeline.
This map stores how the active event count changes at each timestamp.
timeline[start] += 1timeline[end] -= 1
The map acts like a sparse difference array. 2. When a new booking arrives, update the map.
For interval [startTime, endTime):
- Increase the count at
startTime - Decrease the count at
endTime
This means an event becomes active at startTime and stops being active at endTime.
3. Sort all timestamps in ascending order.
We must process time points chronologically because overlap counts depend on accumulated changes over time. 4. Perform a prefix sum sweep.
Maintain:
current_overlap, the number of active events currentlymax_overlap, the highest overlap seen so far
For each timestamp:
- Add the timeline change to
current_overlap - Update
max_overlap
- Return
max_overlap.
This value represents the maximum number of simultaneously active intervals anywhere in the calendar after the new booking.
Why it works
The algorithm works because interval overlap counts change only at interval boundaries.
Adding +1 at a start time means an interval becomes active. Adding -1 at an end time means an interval stops being active. When we sweep through time in sorted order, the running prefix sum always equals the number of active intervals at that moment.
Therefore, the maximum prefix sum encountered during the sweep is exactly the maximum overlap count.
Python Solution
from collections import defaultdict
from typing import DefaultDict
class MyCalendarThree:
def __init__(self):
self.timeline: DefaultDict[int, int] = defaultdict(int)
def book(self, startTime: int, endTime: int) -> int:
self.timeline[startTime] += 1
self.timeline[endTime] -= 1
current_overlap = 0
max_overlap = 0
for time in sorted(self.timeline):
current_overlap += self.timeline[time]
max_overlap = max(max_overlap, current_overlap)
return max_overlap
# Your MyCalendarThree object will be instantiated and called as such:
# obj = MyCalendarThree()
# param_1 = obj.book(startTime,endTime)
The implementation closely follows the sweep line algorithm.
The constructor initializes a defaultdict(int) named timeline. This structure stores net changes in active interval counts at each timestamp.
Inside book, we record the interval boundaries:
+1atstartTime-1atendTime
After updating the map, we sweep through all timestamps in sorted order. The variable current_overlap stores how many intervals are currently active, while max_overlap stores the best answer seen during the sweep.
Because the number of timestamps is small, sorting on every booking is acceptable.
Go Solution
package main
import "sort"
type MyCalendarThree struct {
timeline map[int]int
}
func Constructor() MyCalendarThree {
return MyCalendarThree{
timeline: make(map[int]int),
}
}
func (this *MyCalendarThree) Book(startTime int, endTime int) int {
this.timeline[startTime]++
this.timeline[endTime]--
times := make([]int, 0, len(this.timeline))
for time := range this.timeline {
times = append(times, time)
}
sort.Ints(times)
currentOverlap := 0
maxOverlap := 0
for _, time := range times {
currentOverlap += this.timeline[time]
if currentOverlap > maxOverlap {
maxOverlap = currentOverlap
}
}
return maxOverlap
}
/**
* Your MyCalendarThree object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Book(startTime,endTime);
*/
The Go implementation mirrors the Python solution but requires explicit map and slice handling.
Go maps are unordered, so we first collect all timestamps into a slice and sort them using sort.Ints.
The overlap counting logic is identical. Integer overflow is not an issue because the maximum overlap is bounded by the number of bookings, which is at most 400.
Worked Examples
Example 1
Operations:
book(10, 20)
book(50, 60)
book(10, 40)
book(5, 15)
book(5, 10)
book(25, 55)
Step 1, book(10, 20)
Timeline updates:
| Time | Change |
|---|---|
| 10 | +1 |
| 20 | -1 |
Sweep:
| Time | Running Overlap | Max |
|---|---|---|
| 10 | 1 | 1 |
| 20 | 0 | 1 |
Return 1.
Step 2, book(50, 60)
Timeline:
| Time | Change |
|---|---|
| 10 | +1 |
| 20 | -1 |
| 50 | +1 |
| 60 | -1 |
Sweep:
| Time | Running Overlap | Max |
|---|---|---|
| 10 | 1 | 1 |
| 20 | 0 | 1 |
| 50 | 1 | 1 |
| 60 | 0 | 1 |
Return 1.
Step 3, book(10, 40)
Timeline:
| Time | Change |
|---|---|
| 10 | +2 |
| 20 | -1 |
| 40 | -1 |
| 50 | +1 |
| 60 | -1 |
Sweep:
| Time | Running Overlap | Max |
|---|---|---|
| 10 | 2 | 2 |
| 20 | 1 | 2 |
| 40 | 0 | 2 |
| 50 | 1 | 2 |
| 60 | 0 | 2 |
Return 2.
Step 4, book(5, 15)
Timeline:
| Time | Change |
|---|---|
| 5 | +1 |
| 10 | +2 |
| 15 | -1 |
| 20 | -1 |
| 40 | -1 |
| 50 | +1 |
| 60 | -1 |
Sweep:
| Time | Running Overlap | Max |
|---|---|---|
| 5 | 1 | 1 |
| 10 | 3 | 3 |
| 15 | 2 | 3 |
| 20 | 1 | 3 |
| 40 | 0 | 3 |
| 50 | 1 | 3 |
| 60 | 0 | 3 |
Return 3.
Step 5, book(5, 10)
Timeline changes:
+1at5-1at10
Sweep maximum remains 3.
Return 3.
Step 6, book(25, 55)
Sweep maximum remains 3.
Return 3.
Final outputs:
[1, 1, 2, 3, 3, 3]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n log n) per booking | Sorting all boundary points each call |
| Space | O(n) | Stores interval boundary changes |
Let n be the number of bookings.
Each booking introduces at most two new timestamps. Therefore, the timeline map contains at most 2n keys.
For every book call:
- We insert two map updates in
O(1) - We sort all timestamps in
O(n log n) - We perform a linear sweep in
O(n)
Thus, the dominant cost is sorting.
Since the constraint allows at most 400 bookings, this solution is efficient enough.
Test Cases
# Provided example
calendar = MyCalendarThree()
assert calendar.book(10, 20) == 1 # first interval
assert calendar.book(50, 60) == 1 # no overlap
assert calendar.book(10, 40) == 2 # overlap with first
assert calendar.book(5, 15) == 3 # triple overlap
assert calendar.book(5, 10) == 3 # endpoint touch only
assert calendar.book(25, 55) == 3 # overlap but max unchanged
# Non-overlapping intervals
calendar = MyCalendarThree()
assert calendar.book(1, 5) == 1
assert calendar.book(6, 10) == 1
assert calendar.book(11, 15) == 1
# Fully overlapping intervals
calendar = MyCalendarThree()
assert calendar.book(10, 20) == 1
assert calendar.book(10, 20) == 2
assert calendar.book(10, 20) == 3
assert calendar.book(10, 20) == 4
# Endpoint touching intervals
calendar = MyCalendarThree()
assert calendar.book(10, 20) == 1
assert calendar.book(20, 30) == 1
assert calendar.book(30, 40) == 1
# Nested intervals
calendar = MyCalendarThree()
assert calendar.book(1, 100) == 1
assert calendar.book(20, 80) == 2
assert calendar.book(30, 70) == 3
assert calendar.book(40, 60) == 4
# Large coordinate values
calendar = MyCalendarThree()
assert calendar.book(0, 10**9) == 1
assert calendar.book(1, 10**9 - 1) == 2
# Mixed overlaps
calendar = MyCalendarThree()
assert calendar.book(5, 15) == 1
assert calendar.book(10, 20) == 2
assert calendar.book(15, 25) == 2
assert calendar.book(12, 18) == 3
| Test | Why |
|---|---|
| Provided example | Verifies standard overlapping behavior |
| Non-overlapping intervals | Ensures no false overlap counting |
| Fully overlapping intervals | Tests increasing overlap counts |
| Endpoint touching intervals | Validates half open interval semantics |
| Nested intervals | Confirms deep overlap handling |
| Large coordinate values | Ensures sparse timeline logic works |
| Mixed overlaps | Tests complex overlap transitions |
Edge Cases
Intervals Touching at Endpoints
A very common bug is incorrectly treating [10, 20) and [20, 30) as overlapping.
Because the interval is half open, the first interval ends exactly when the second begins. The implementation handles this naturally by applying -1 at 20 and +1 at 20. During the sweep, the prefix sum correctly reflects that the intervals do not overlap simultaneously.
Multiple Identical Intervals
If many identical intervals are booked, the overlap count should continue increasing.
For example:
[10, 20)
[10, 20)
[10, 20)
The difference map accumulates multiple +1 and -1 changes at the same timestamps. The sweep line correctly computes overlaps of 1, 2, and 3.
Extremely Large Time Values
The timestamps can be as large as 10^9.
A naive array based solution would be impossible because allocating memory proportional to the timeline size would be enormous. The sweep line approach avoids this issue entirely because it stores only boundary points that actually appear in bookings.