Sponsored
Sponsored
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 constructor() {
3 this.timeline = [];
4 }
5
6 book(start, end) {
7 this.timeline.push([start, 1]);
8 this.timeline.push([end, -1]);
9
10 this.timeline.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
11
12 let maxK = 0, currentK = 0;
13 for (let i = 0; i < this.timeline.length; i++) {
14 currentK += this.timeline[i][1];
15 maxK = Math.max(maxK, currentK);
16 }
17 return maxK;
18 }
19}In JavaScript, we use the Array to manage time events and perform sort on it based on time values. Running total of events gives the maximum overlapping interval.
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.
1#include <map>
2using namespace std;
3
4class MyCalendarThree {
5 map<int, int> timeline;
public:
MyCalendarThree() {}
int book(int start, int end) {
timeline[start]++;
timeline[end]--;
int maxK = 0, active = 0;
for (auto& [time, count] : timeline) {
active += count;
maxK = max(maxK, active);
}
return maxK;
}
};This C++ implementation employs std::map as a balanced tree to store the impact (+1, -1) at each start and end time. It iterates over the sorted keys to measure the overlapping events count.