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 between all the previous events.
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.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 <= 109400 calls will be made to book.In #732 My Calendar III, each booking adds a time interval and you must return the maximum number of overlapping events after every insertion. The key idea is to treat bookings as a sweep line problem. Instead of tracking each interval separately, record +1 at the start time and −1 at the end time using an ordered map. By computing a running prefix sum over these points, you can determine how many events are active at any moment, and the maximum value represents the current overlap.
Another scalable strategy uses a Segment Tree with lazy propagation. This structure efficiently handles range updates and tracks the maximum overlap across a large time domain. Each booking updates the interval count, and the tree maintains the global maximum.
The sweep-line approach is simpler to implement for moderate constraints, while the segment tree approach is more robust for large ranges and repeated queries. Both rely on efficiently maintaining cumulative overlaps.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sweep Line with Ordered Map | O(n log n) overall due to ordered updates and prefix traversal | O(n) |
| Segment Tree with Lazy Propagation | O(log R) per booking update | O(R) depending on coordinate range or compressed nodes |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Treat each interval [start, end) as two events "start" and "end", and process them in sorted order.
This method uses a line sweep technique, where we process the critical points along the time axis. We treat each event start time as a +1 (which indicates a new event starts), and each end time as a -1 (indicating an event ends).
By maintaining a running sum, we can identify the maximum overlap of events, which gives us the maximum k-booking at any point.
Time Complexity: O(N log N) due to sorting.
Space Complexity: O(N) for storing the timeline of events, where N is the number of events booked.
1class MyCalendarThree:
2 def __init__(self):
3 self.timeline = []
4
5 def book(self, start: int, end: int) -> int:
6 self.timeline.append((start, 1))
7 self.timeline.append((end, -1))
8
9 self.timeline.sort()
10
11 max_k, current_k = 0, 0
12 for time, value in self.timeline:
13 current_k += value
14 max_k = max(max_k, current_k)
15
16 return max_kIn this Python implementation, we maintain a list of tuples representing time points and their effects (+1 or -1). We sort these time points and iterate over them to calculate the maximum overlapping intervals, thus obtaining the maximum k-booking.
A more advanced approach involves using a balanced tree map (or balanced tree data structure) to manage events and efficiently find the maximum overlap.
The map holds start and end times as keys and their occurrences as values. By efficiently summing these up, we can determine the maximum k-booking.
Time Complexity: O(N log N) for the operations on a balanced tree.
Space Complexity: O(N) traversing the sorted keys when booking new events.
1using System;
2using System.Collections.Generic;
3
4public class MyCalendarThree {
5 private SortedDictionary<int, int> timeline;
public MyCalendarThree() {
timeline = new SortedDictionary<int, int>();
}
public int Book(int start, int end) {
if (!timeline.ContainsKey(start)) timeline[start] = 0;
if (!timeline.ContainsKey(end)) timeline[end] = 0;
timeline[start]++;
timeline[end]--;
int active = 0, maxK = 0;
foreach (var entry in timeline) {
active += entry.Value;
maxK = Math.Max(maxK, active);
}
return maxK;
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Prefix sums allow you to accumulate the net changes in bookings over time. By adding +1 at a start point and −1 at an end point, the running sum directly represents how many events are currently active.
Yes, interval scheduling and sweep line problems like My Calendar III are common in FAANG-style interviews. They test understanding of data structures such as ordered maps, segment trees, and interval processing techniques.
Two popular data structures are an ordered map (such as TreeMap) and a segment tree with lazy propagation. The ordered map works well for sweep line processing, while a segment tree efficiently handles range updates and queries over large time intervals.
A common optimal approach uses a sweep line technique with an ordered map to track +1 at start times and −1 at end times. By maintaining a running prefix sum, you can determine the number of active bookings at any time and keep track of the maximum overlap.
This C# solution uses a SortedDictionary to act like a balanced binary search tree. We increment the value for a start time and decrement for an end time. The running sum of values reflects the number of active events at any time.