[Hard] 732. My Calendar III

A k-booking happens when k events have some non-empty intersection (i.e., there is some time that is common to all k events).

You are given some events [startTime, endTime), after each given event, return an integer k representing the maximum k-booking from all the previous events.

Your event will be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.

Implement the MyCalendarThree class:

MyCalendarThree() Initializes the object.
int book(int startTime, int endTime) Returns an integer k representing the largest integer such that there exists a k-booking in the calendar.

Examples

Example 1:

Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]

Explanation
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // return 1
myCalendarThree.book(50, 60); // return 1
myCalendarThree.book(10, 40); // return 2
myCalendarThree.book(5, 15);  // return 3
myCalendarThree.book(5, 10);  // return 3
myCalendarThree.book(25, 55); // return 3

Constraints

0 <= startTime < endTime <= 10^9
At most 400 calls will be made to book.

Thinking Process

Sweep Line: Most intuitive, tracks active bookings at each time point

The search space must shrink monotonically each step.
Decide which half still satisfies the predicate, discard the other.
Use mid = left + (right - left) / 2 to avoid overflow.

Common Approaches

Typical techniques for this pattern:

Approach	Time	Space	Notes
Standard binary search (this problem)	O(log n)	O(1)	Sorted array, `left <= right`
Lower / upper bound	O(log n)	O(1)	First/last position, insert index
Binary search on rotated array	O(log n)	O(1)	Identify sorted half, discard other
Binary search on answer	O(n log M)	O(1)	Monotonic predicate over search space

Solution

Solution 1: Sweep Line / Difference Array (Map)

Use an ordered map to track interval boundaries and sweep to find maximum overlap.

class MyCalendarThree:
MyCalendarThree() :
def book(self, startTime, endTime):
    mp[startTime]++
    mp[endTime]--
    maxBooking = 0
    active = 0
    for([time, curr] : mp) :
    active += curr
    maxBooking = max(maxBooking, active)
return maxBooking
map<int, int> mp
/
 Your MyCalendarThree object will be instantiated and called as such:
 MyCalendarThree obj = new MyCalendarThree()
 param_1 = obj.book(startTime, endTime)
/

Solution Explanation

Approach: Standard binary search (this problem)

Key idea: 1. Sweep Line: Most intuitive, tracks active bookings at each time point

How the code works:

Sweep Line: Most intuitive, tracks active bookings at each time point
- The search space must shrink monotonically each step.
- Decide which half still satisfies the predicate, discard the other.
- Use mid = left + (right - left) / 2 to avoid overflow.

Algorithm Explanation:

Difference Array:
- mp[startTime]++: Mark interval start (+1)
- mp[endTime]--: Mark interval end (-1)
Sweep Line:
- Iterate through sorted time points
- Accumulate active bookings: active += curr
- Track maximum: maxBooking = max(maxBooking, active)
Why It Works:
- Each start adds 1 to active count
- Each end subtracts 1 from active count
- Maximum active count = maximum overlap

Example Walkthrough:

Input: book(10, 20), book(50, 60), book(10, 40)

Step 1: book(10, 20)
  mp[10] = 1, mp[20] = -1
  Sweep: active = 0 → 1 (at 10) → 0 (at 20)
  maxBooking = 1 ✓

Step 2: book(50, 60)
  mp[50] = 1, mp[60] = -1
  Sweep: active = 0 → 1 (at 10) → 0 (at 20) → 1 (at 50) → 0 (at 60)
  maxBooking = 1 ✓

Step 3: book(10, 40)
  mp[10] = 2, mp[40] = -1
  Sweep: active = 0 → 2 (at 10) → 1 (at 20) → 0 (at 40) → 1 (at 50) → 0 (at 60)
  maxBooking = 2 ✓

Complexity Analysis:

Time Complexity: O(n log n) per book() call
- Map insertion: O(log n)
- Iteration over map: O(n) where n = number of unique time points
- Overall: O(n log n)
Space Complexity: O(n)
- Store up to 2n time points (start and end for each booking)
- Overall: O(n)

Solution 2: Segment Tree with Lazy Propagation

Use segment tree for range updates and maximum queries over large ranges.

class MyCalendarThree:
MyCalendarThree() :
def book(self, startTime, endTime):
    update(startTime, endTime - 1, 1, 1e9, 1)
    return vals[1]
dict[int, int> vals
dict[int, int> lazy
max_len = 1e9
def update(self, start, end, left, right, idx):
    if(start > right  or  end < left) return
    if left >= start  and  right <= end:
        lazy[idx]++
        vals[idx]++
         else :
        mid = (left + right) / 2
        update(start, end, left, mid, idx  2)
        update(start, end, mid + 1, right, idx  2 + 1)
        vals[idx] = lazy[idx] + max(vals[idx  2], vals[idx  2 + 1])
/
 Your MyCalendarThree object will be instantiated and called as such:
 MyCalendarThree obj = new MyCalendarThree()
 param_1 = obj.book(startTime, endTime)
/

Algorithm Explanation:

Lazy Propagation: Defer updates to children until needed
Range Update: Update range [start, end-1] with +1
Maximum Query: Root node stores maximum overlap
Dynamic Nodes: Use unordered_map for sparse segment tree

Complexity Analysis:

Time Complexity: O(log M) per book() call
- M = range size (10^9)
- Each update traverses tree height: O(log M)
Space Complexity: O(n log M)
- n = number of bookings
- Each booking creates O(log M) nodes
- Overall: O(n log M)

Solution 3: Split Intervals (Line Sweep)

Split intervals at boundaries and maintain active counts.

class MyCalendarThree:
MyCalendarThree() :
starts[0] = 0
starts[(int)1e9 + 1] = 0
maxBooking = 0
def book(self, startTime, endTime):
    split(startTime)
    split(endTime)
    for(it = starts.find(startTime) it.first < endTime it += 1) :
    maxBooking = max(maxBooking, ++(it.second))
return maxBooking
map<int, int> starts
maxBooking
def split(self, x):
    starts[x] = (starts -= 1.upper_bound(x)).second
/
 Your MyCalendarThree object will be instantiated and called as such:
 MyCalendarThree obj = new MyCalendarThree()
 param_1 = obj.book(startTime, endTime)
/

Algorithm Explanation:

Split Function:
- split(x) ensures interval starting at x exists
- Copies count from previous interval
Book Function:
- Split at start and end boundaries
- Increment count for all intervals in [start, end)
- Track maximum booking
Why It Works:
- Maintains intervals between boundaries
- Each interval has a count
- Maximum count = maximum overlap

Example Walkthrough:

Input: book(10, 20), book(10, 40)

Step 1: book(10, 20)
  split(10): starts[10] = starts[0] = 0
  split(20): starts[20] = starts[10] = 0
  Increment [10, 20): starts[10] = 1
  maxBooking = 1 ✓

Step 2: book(10, 40)
  split(10): already exists
  split(40): starts[40] = starts[20] = 0
  Increment [10, 40): 
    starts[10] = 2
    starts[20] = 1 (new interval)
  maxBooking = 2 ✓

Complexity Analysis:

Time Complexity: O(n) per book() call
- Split: O(log n) for map operations
- Iteration: O(n) for intervals in range
- Overall: O(n)
Space Complexity: O(n)
- Store up to 2n boundaries
- Overall: O(n)
  Common Mistakes

Single booking: book(10, 20) → return 1
No overlap: book(10, 20), book(30, 40) → return 1
Complete overlap: book(10, 20), book(10, 20) → return 2
Partial overlap: book(10, 30), book(20, 40) → return 2
Multiple overlaps: book(10, 20), book(15, 25), book(18, 22) → return 3
Inclusive end: Treating end as inclusive instead of exclusive
Not tracking maximum: Forgetting to update maximum after each booking
Segment tree range: Using [start, end] instead of [start, end-1]
Split logic: Not properly splitting intervals at boundaries
Iterator errors: Invalidating iterators during iteration

LC 729: My Calendar I - Check for any overlap
LC 731: My Calendar II - Allow double booking, prevent triple
LC 56: Merge Intervals - Merge overlapping intervals
LC 218: The Skyline Problem - Similar sweep line approach

Key Takeaways

Sweep Line: Most intuitive, tracks active bookings at each time point
Segment Tree: Efficient for large ranges, supports range updates
Split Intervals: Maintains explicit intervals with counts
Half-Open Intervals: End is exclusive, so [10, 20) and [20, 30) don’t overlap
Maximum Tracking: Need to track maximum across all time points

References

LC 732: My Calendar III on LeetCode
LeetCode Discuss — LC 732: My Calendar III
LeetCode Editorial (may require premium)

Template Reference

Array & Matrix

Robina Li

[Hard] 732. My Calendar III

Examples

Constraints

Thinking Process

Common Approaches

Solution

Solution 1: Sweep Line / Difference Array (Map)

Solution Explanation

Algorithm Explanation:

Example Walkthrough:

Complexity Analysis:

Solution 2: Segment Tree with Lazy Propagation

Algorithm Explanation:

Complexity Analysis:

Solution 3: Split Intervals (Line Sweep)

Algorithm Explanation:

Example Walkthrough:

Complexity Analysis:

Common Mistakes

Key Takeaways

References

Template Reference

Related Posts

Recent Posts

Examples

Constraints

Thinking Process

Common Approaches

Solution

Solution 1: Sweep Line / Difference Array (Map)

Solution Explanation

Algorithm Explanation:

Example Walkthrough:

Complexity Analysis:

Solution 2: Segment Tree with Lazy Propagation

Algorithm Explanation:

Complexity Analysis:

Solution 3: Split Intervals (Line Sweep)

Algorithm Explanation:

Example Walkthrough:

Complexity Analysis:

Common Mistakes

Related Problems

Key Takeaways

References

Template Reference

Related Posts

Recent Posts