Hex.*

LC729 - My Calendar I

Posted on In
Leetcode: 141/2658 (57+68+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 double booking.
A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both 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 MyCalendar class:
MyCalendar() 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 double booking. Otherwise, return false and do not add the event to the calendar.

Example 1:
Input
[“MyCalendar”, “book”, “book”, “book”]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]
Explanation
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.

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

Solutions

Brute Force

  • Check whether [start, end] can be added to MyCalendar, which can be compared by comparing the relationship between [s,e] and [start, end]
    • e ≤ start or end ≤ s are all satisfied
    • That is, e > start and end > s, there is overlap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#O(n^2) time | O(n) space
class MyCalendar:

    def __init__(self):
        self.booking = []

    def book(self, start: int, end: int) -> bool:
        for s, e in self.booking:
            if e <= start:
                continue
            if s >= end:
                continue
            return False
        self.booking.append((start, end))
        return True
        

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

SortedDict

Similar to the first method, but this method uses a SortedDict to store the data. This ordered dictionary is useful for handling boundaries in the next method.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# O(n^2) time | O(n) space
from sortedcontainers import SortedDict
class MyCalendar:

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

    def book(self, start: int, end: int) -> bool:
        for s, e in self.booking.items():
            if e <= start:
                continue
            if s >= end:
                continue
            return False
        self.booking[start] = end
        return True
        

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

Difference Array

This method can be used in MyCalendar2 and MyCalendar3

  • 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 there is overlap, 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
31
# O(n^2) time | O(n) space
from sortedcontainers import SortedDict
class MyCalendar:

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

    def book(self, start: int, end: int) -> bool:
        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
        for i,v in self.booking.items():
            presum+=v
            if presum > 1:
                self.booking[start] -=1
                self.booking[end] +=1
                return False
        return True
       

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