Last updated on March 2nd, 2025 at 02:50 pm

Here, we see a My Calendar III LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Ordered Map, Segment Tree

Level of Question

Hard

My Calendar III LeetCode Solution

1. Problem Statement

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

2. Coding Pattern Used in Solution

The provided code in all four languages uses the Sweep Line Algorithm pattern. This pattern is commonly used in interval problems where events are processed in a sorted order of their start and end times. The algorithm keeps track of the number of active intervals (or overlaps) at any given point in time and determines the maximum overlap.

3. Code Implementation in Different Languages

3.1 My Calendar III C++

class MyCalendarThree {
public:
    MyCalendarThree() {}
    
    int book(int start, int end) {
        lines[start]++;
        lines[end]--;
        int mx = 0, cnt = 0;
        for (auto x : lines) {
            cnt += x.second;
            mx = max(mx, cnt);
        }
        return mx;
    }
private:
    map<int, int> lines;
};

3.2 My Calendar III Java

class MyCalendarThree {
    private TreeMap<Integer, Integer> lines;
   
    public MyCalendarThree() {
        lines = new TreeMap<>();
    }
    
    public int book(int start, int end) {
        lines.put(start, lines.getOrDefault(start, 0) + 1);
        lines.put(end, lines.getOrDefault(end, 0) - 1);
        int mx = 0, cnt = 0;
        for (int x : lines.values()) {
            cnt += x;
            mx = Math.max(mx, cnt);
        }
        return mx;
    }    
}

3.3 My Calendar III JavaScript

var MyCalendarThree = function() {
    this.tm = {}
};

MyCalendarThree.prototype.book = function(start, end) {
    this.tm[start] = (this.tm[start] || 0) + 1
    this.tm[end] = (this.tm[end] || 0) - 1
    let max = count = 0
    for(let val in this.tm){
        max = Math.max(max, count += this.tm[val])
    }
    return max
};

3.4 My Calendar III Python

class MyCalendarThree(object):

    def __init__(self):
        self.maxOverlaps = 1
        self.bookings = []

    def checkOverlaps_boundryCount(self):
        lst = []
        for start, end in self.bookings:
            lst.append((start, +1))
            lst.append((end, -1))
        lst.sort()
        
        overlaps = 0
        for b in lst:
            overlaps += b[1]
            self.maxOverlaps = max(self.maxOverlaps, overlaps)
        return self.maxOverlaps
		
    def book(self, start, end):
       self.bookings.append((start, end))
       return self.checkOverlaps_boundryCount()

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n log n)	O(n)
Java	O(n log n)	O(n)
JavaScript	O(n log n)	O(n)
Python	O(n log n)	O(n)

• The code efficiently calculates the maximum number of overlapping intervals using the Sweep Line Algorithm.
• It leverages sorted data structures (map, TreeMap, dictionary, or list) to process events in chronological order and compute overlaps dynamically.