Hex.*

LC732 - My Calenar III

Posted on In
Leetcode: 143/2658 (57+69+17)

Description

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.

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, 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

Constraints:
0 <= start < end <= 109
At most 400 calls will be made to book.

Solution

  • A sorted dictionary needs to be maintained, where the key is the value of start and end in each time period, and the value is the number of occurrences corresponding to it
  • In differential thinking, we only need to maintain start and end (end is not included). Just set start +=1, end -=1
  • Then add them one by one using the prefix sum, so you can know how many times this schedule overlaps. According to the meaning of the question, keep the maximum value and return the maximum value.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# O(n^2) time | O(n) space
from sortedcontainers import SortedDict
class MyCalendarThree:
    def __init__(self):
        self.booking = SortedDict()

    def book(self, start: int, end: int) -> int:
        if start not in self.booking:
            self.booking[start] = 1
        else:
            self.booking[start] +=1
        
        if end not in self.booking:
            self.booking[end] =-1
        else:
            self.booking[end] -=1
        
        presum = 0
        ans = 0
        for i, v in self.booking.items():
            presum += v
            ans = max(ans, presum)
        return ans

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