Leetcode 732. My Calendar III
Problem Explanation
The problem is asking us to implement a class MyCalendarThree
which allows us to book events. We should always be able to add a new event, no matter what.
Each event is defined by a start time and an end time. These times reflect a half open interval, meaning that the start time is included in the event, but the end time isn't. So if an event starts at 10 and ends at 20, the event covers the time from 10 to just before 20.
The class MyCalendarThree
should have one method called book
that takes two parameters - start
and end
of an event.
A special type of event booking is a K-booking, which happens when K events have some common interval. The book
method should return the maximum value of K, where a K-booking exists in the calendar till now.
Solution Approach
The solution uses Sweep Line algorithm for this problem, which uses a map
data structure to implement it. The map
data structure named timeline
is used to store the start and end points of the intervals with their counts.
For each book
call, we increase the count of start point and decrease the count of end point in timeline
.
Next, we iterate over timeline
and for each point, we maintain a counter for active events.
Finally, the active events count gives us the maximum K-booking at any point of time.
Python Solution
1 2python 3from collections import Counter 4 5class MyCalendarThree: 6 7 def __init__(self): 8 self.timeline = Counter() 9 10 def book(self, start: int, end: int) -> int: 11 self.timeline[start] += 1 # increment the start point 12 self.timeline[end] -= 1 # decrement the end point 13 14 active = ans = 0 15 for x in sorted(self.timeline): 16 active += self.timeline[x] 17 if active > ans: 18 ans = active 19 20 return ans
Java Solution
1
2java
3class MyCalendarThree {
4 private TreeMap<Integer, Integer> calendar;
5
6 public MyCalendarThree() {
7 calendar = new TreeMap<>();
8 }
9
10 public int book(int start, int end) {
11 calendar.put(start, calendar.getOrDefault(start, 0) + 1);
12 calendar.put(end, calendar.getOrDefault(end, 0) - 1);
13
14 int active = 0, ans = 0;
15 for (int k: calendar.values()) {
16 active += k;
17 if (active > ans) {
18 ans = active;
19 }
20 }
21
22 return ans;
23 }
24}
JavaScript Solution
1 2javascript 3class MyCalendarThree { 4 constructor() { 5 this.timeline = new Map(); 6 } 7 8 book(start, end) { 9 this.timeline.set(start, (this.timeline.get(start) || 0) + 1); 10 this.timeline.set(end, (this.timeline.get(end) || 0) - 1); 11 12 let active = 0, ans = 0; 13 Array.from(this.timeline.entries()).sort().forEach(([k, v]) => { 14 active += v; 15 ans = Math.max(ans, active); 16 }); 17 18 return ans; 19 } 20}
C++ Solution
1
2cpp
3class MyCalendarThree {
4 map<int, int> timeline;
5
6public:
7 MyCalendarThree() {
8 }
9
10 int book(int start, int end) {
11 ++timeline[start];
12 --timeline[end];
13 int active = 0, ans = 0;
14 for(auto kv : timeline) {
15 active += kv.second;
16 ans = max(ans, active);
17 }
18 return ans;
19 }
20};
C# Solution
1
2csharp
3public class MyCalendarThree
4{
5 private SortedDictionary<int, int> timeline;
6
7 public MyCalendarThree()
8 {
9 timeline = new SortedDictionary<int, int>();
10 }
11
12 public int Book(int start, int end)
13 {
14 if (!timeline.ContainsKey(start)) timeline[start] = 0;
15 timeline[start]++;
16 if (!timeline.ContainsKey(end)) timeline[end] = 0;
17 timeline[end]--;
18
19 int active = 0, ans = 0;
20 foreach(var val in timeline.Values)
21 {
22 active += val;
23 ans = Math.Max(ans, active);
24 }
25
26 return ans;
27 }
28}
In all solutions, the timeline
map stores the changes in the count of bookings. With start times, bookings increase, hence increment the count. With end times, a booking ends, so decrement the count. The active variable counts the ongoing bookings at any instance of time. The maximum value this variable takes is the maximum k-booking at any point of time.
Note:
Counter
in Python and TreeMap
in Java are similar to the map
in C++ and C#'s SortedDictionary
.
JavaScript's Map
objects preserve the insertion order of the keys. Hence, we explicitly have to sort the keys while iterating over them.
Go Solution
1 2go 3type MyCalendarThree struct { 4 timeline map[int]int 5} 6 7func Constructor() MyCalendarThree { 8 return MyCalendarThree{timeline: make(map[int]int)} 9} 10 11func (this *MyCalendarThree) Book(start int, end int) int { 12 // increment start point 13 this.timeline[start]++ 14 // decrement end point 15 this.timeline[end]-- 16 17 active := 0 18 max := 0 19 keys := []int{} 20 for k := range this.timeline { 21 keys = append(keys, k) 22 } 23 sort.Ints(keys) 24 for _, k := range keys { 25 active += this.timeline[k] 26 if active > max { 27 max = active 28 } 29 } 30 return max 31}
GoLang Solution Explanation
In this GoLang solution, we utilize the map
data structure to store our timeline.
The Book
function first increments the value of the start point and decrements the value of the end point in our timeline.
We then initialize active
and max
as 0.
We need to look at our timeline in order. To do this, we get all the keys from our timeline and sort them in ascending order.
Then, for each point in our timeline in ascending order, we increment active
by the value of the point in our timeline.
If active
is greater than max
, then we update max
to be active
.
At the end of our function, max
will hold the maximum K-booking.
Note: The built-in Go map
does not maintain any order of its keys. Hence, we need to sort the keys before iterating over them, which is different than Python's Counter,
Java's TreeMap
, JavaScript's Map
, C++'s map
and C#'s SortedDictionary
.
Conclusion
All these solutions implement a similar logic using the appropriate data structures available in their respective languages to solve the problem. They ensure that new events can always be added and the maximum value of K for a K-booking can be tracked and returned.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.