My Calender III

Question states to create a class called my calendar III which has a function which adds bookings to the calendar. When you add a booking with a start and end time, which are integers, you have to return the max number of intersections between the bookings for the calender.

Ex. Let’s say the bookings are as follows:

• [10, 20]
• [15, 30]
• [40, 50]
• [3, 18]

The first booking would return 1, because the max number of intersections would be itself intersected. The second booking would return 2, because 10, 20 intersects with 15, 30 The third booking would return 2, because 10, 20 x 15, 30 and nothing intersects with 40, 50 The fourth booking would return 3, because 3, 18 x 10, 20 x 15, 30 (x = intersects)

00000000011111111111000000000000000000000000000000
00000000000000111111111111111111110000000000000000
00000000000000000000000000000000000000011111111111
00111111111111111100000000000000000000000000000000

Doing a linear scan from left to right across each column, you can tell the three is the maximum intersection because the end of any list comes before the 3rd beginning. Indeed, at 15 you can tell that all three ranges are valid, but the only information you need are the starts and ends.

Pseudocode

declare class
    class construction 
        create hashmap/dictionary
    function book which accepts start and end
        use class dictionary to record start times and end times
        start times will have value 1 for each whereas end times will have value -1
        go thru sorted dictionary (left to right)
            save a total running sum of the start times and end times
            save a maximum variable for the maximum intersections
        return the maximum variable

Python

This is what the code would look like.

class MyCalendarThree:

    def __init__(self):
        self.d = defaultdict(int)

    def book(self, start: int, end: int) -> int:
        self.d[start] += 1
        self.d[end] -= 1
        total = 0
        maximum = 0
        for key in sorted(self.d.keys()):
            total += self.d[key]
            maximum = max(total, maximum)
        return maximum

# Your MyCalendarThree object will be instantiated and called as such:
# obj = MyCalendarThree()
# param_1 = obj.book(start,end)

Results

Runtime: 4563 ms, faster than 5.23% of Python3 online submissions for My Calendar III.

Memory Usage: 14.3 MB, less than 92.31% of Python3 online submissions for My Calendar III.

Complexity Analysis:

Let’s say we have n bookings. This means we have 2*n keys in the dictionary assuming worst case scenario where each key is unique. This means that we have to sort which best case scenario for sorting is O(nlogn) which means the function has a complexity of \(\Theta(4n^2log(2n))\) This means the big O value is \(\Omicron(n^2logn)\), because constants don’t matter after extremely large n \(4n^2log(2n) \le n^2logn\)

Faster solutions use SortedDict, which adds the key in its sorted position, rather than sorts the whole key list everytime book is called. This would be the optimal solution.