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.