Hex.*

LC731 - My Calendar II

Posted on In
Leetcode: 142/2658 (57+69+16)

Description

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a triple booking.
A triple booking happens when three events have some non-empty intersection (i.e., some moment is common to all the three events.).
The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.
Implement the MyCalendarTwo class:
MyCalendarTwo() Initializes the calendar object.
boolean book(int start, int end) Returns true if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return false and do not add the event to the calendar.

Example 1:
Input
[“MyCalendarTwo”, “book”, “book”, “book”, “book”, “book”, “book”]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]
Explanation
MyCalendarTwo myCalendarTwo = new MyCalendarTwo();
myCalendarTwo.book(10, 20); // return True, The event can be booked.
myCalendarTwo.book(50, 60); // return True, The event can be booked.
myCalendarTwo.book(10, 40); // return True, The event can be double booked.
myCalendarTwo.book(5, 15); // return False, The event cannot be booked, because it would result in a triple booking.
myCalendarTwo.book(5, 10); // return True, The event can be booked, as it does not use time 10 which is already double booked.
myCalendarTwo.book(25, 55); // return True, The event can be booked, as the time in [25, 40) will be double booked with the third event, the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.

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

Solutions

  • 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, if the overlap value > 2, return False.
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
28
29
30
#O(n^2) time | O(n) space
from sortedcontainers import SortedDict
class MyCalendarTwo:

    def __init__(self):
        self.booking = SortedDict()

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

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