My Calendar 3

Problem

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 [start, end), 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 start, int end) Returns an integer k representing the largest integer such that there exists a k-booking in the calendar.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


**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, The first event can be booked and is disjoint, so the maximum k-booking is a 1-booking.
myCalendarThree.book(50, 60); // return 1, The second event can be booked and is disjoint, so the maximum k-booking is a 1-booking.
myCalendarThree.book(10, 40); // return 2, The third event [10, 40) intersects the first event, and the maximum k-booking is a 2-booking.
myCalendarThree.book(5, 15); // return 3, The remaining events cause the maximum K-booking to be only a 3-booking.
myCalendarThree.book(5, 10); // return 3
myCalendarThree.book(25, 55); // return 3

Solution

Method 1 - Using TreeMap and Count

To solve this problem, we need to find the maximum number of overlapping intervals (or bookings). The key idea is to use a difference array to track start and end points of intervals and apply an interval sweep technique to calculate the maximum overlap.

We use a TreeMap (Java) or dict (Python) to record the times when intervals start (+1) and end (-1). This allows us to efficiently count overlapping intervals.

We can use solution similar to My Calendar 2#Method 1 - Using TreeMap and Count.Instead of checking for 2, we check for k-1.

Algorithm

Every time an interval [start, end) is added, we update the map by incrementing the start time by 1 (indicating an interval starts) and decrementing the end time by -1 (indicating an interval ends).
To calculate the maximum overlap (k-booking), traverse through the keys of this map in sorted order and maintain a running sum of active intervals. Update the maximum overlap as the running sum evolves.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class MyCalendarThree {

    private TreeMap<Integer, Integer> countMap;

    public MyCalendarThree() {
        countMap = new TreeMap<>();
        ans = 0;
    }

    public int book(int start, int end) {
        countMap.put(start, countMap.getOrDefault(start, 0) + 1);
        countMap.put(end, countMap.getOrDefault(end, 0) - 1);

        int ans = 0;
        int active = 0;
        for (int c : countMap.values()) {
            active += c;
            ans = Math.max(ans, active);
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class MyCalendarThree:
    def __init__(self) -> None:
        self.count_map: Dict[int, int] = {}

    def book(self, start: int, end: int) -> int:
        self.count_map[start] = self.count_map.get(start, 0) + 1
        self.count_map[end] = self.count_map.get(end, 0) - 1
		ans: int = 0
        active: int = 0
        for t in sorted(self.count_map):
            active += self.count_map[t]
            ans = max(self.ans, active)
        
        return ans

Complexity

⏰ Time complexity: O(n). The book method involves updating the map which takes O(log(n)) due to insertion in a sorted map and a sweep over the keys which takes O(n) in the worst case.
- Hence, the time complexity of book is O(n) per call.
🧺 Space complexity: O(n) for storing the map, where n is the number of unique time points.

Problem#

Examples#

Solution#

Method 1 - Using TreeMap and Count#

Algorithm#

Code#

Complexity#