LeetCode 729 My Calendar I

LeetCode

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 <= 10<sup>9</sup> At most 1000 calls will be made to book.

暴力法算法思路(推荐)：

存储所有区间

注意事项：

区间比较难写，用符合加入会议条件的相反来写，not (start >= root.end or end <= root.start)

Python代码：

class MyCalendar(TestCases):

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

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

算法分析：

时间复杂度为O(n²), 空间复杂度O(n)

端点排序法解题思路II：

区间重合题考虑用heap或者端点排序法，输入是必须有序，所以此题可以令区间有序，而heap用于处理重合情况下的计算，此题不适用，所以用端点排序法。

解题步骤：

N/A

注意事项：

区间端点排序，(endpoint, 1/-1), 1表示始点，-1表示终点。用bisect搜索时，注意输入也要用两维(start, 1)
难点在于比较结果决定返回Ture or False。两种情况返回False：好的情况是输入区间的搜索结果的下标应该相等表示可以插入到现有两区间之间，所以若不等，就不符合。第二种是若现有区间完全覆盖新区间，此时搜索结果下标也一样，所以此情况新区间终点的搜索结果(后一个节点)是终点。同时为保证搜索结果不处理越界，加入空端点
若同一个端点同时存在始点和端点，不用合并，因为它们已经按-1, 1排序了。

Python代码：

class MyCalendar(TestCases):

    def __init__(self):
        self.calendar = [(float('-inf'), -1), (float('inf'), 1)]

    def book(self, start: int, end: int) -> bool:
        index_start = bisect.bisect(self.calendar, (start, 1)) # remember params
        index_end = bisect.bisect(self.calendar, (end, -1))
        if index_start != index_end or self.calendar[index_end][1] == -1:
            return False
        # no need to merge endpoints coz they are sorted in (a, -1), (a, 1) as expected
        bisect.insort(self.calendar, (start, 1))
        bisect.insort(self.calendar, (end, -1))
        return True

算法分析：

时间复杂度为O(n²)，由于insort是插入需要移动数组，所以是O(n), 空间复杂度O(n)

线段树算法III思路(不推荐)：

区间重合题考虑用heap类似meeting rooms，输入是必须有序，但这里新区间与已有区间不是有序且不能online处理，所以不能用heap。
考虑用start, end排序，二分法查找，只能处理单次，因为插入不方便。
要查找和插入都能低于O(n)，就只能用TreeMap。类似于线段树存储区间，此题每个Node存储一个区间。新区间的end，start分别与root的start和end比较，若不重合，就递归到左右子树。此树投影为离散且不重合的区间。

注意事项：

考察二叉树插入算法，返回值需要是TreeNode，如root.left = self.dfs(root.left, start, end)。由于需要知道是否成功插入，所以返回值多加一个boolean
区间比较难写，用符合加入会议条件的相反来写，not (start >= root.end or end <= root.start)
is_left or is_right任意一个加入成功都可以，所以是or不是and

Python代码：

class MyCalendar(TestCases):

    def __init__(self):
        self.head = None

    def book(self, start: int, end: int) -> bool:
        root, is_booked = self.dfs(self.head, start, end)
        self.head = root
        return is_booked

    def dfs(self, root, start, end):
        if not root:
            return TreeNode(start, end), True
        #if root.start <= start < root.end or root.start < end <= root.end: # remember
        if not (start >= root.end or end <= root.start):
            return root, False
        is_left = is_right = False
        if end <= root.start:
            root.left, is_left = self.dfs(root.left, start, end)
        else:
            root.right, is_right = self.dfs(root.right, start, end)
        return root, is_left or is_right # remember or

算法分析：

时间复杂度为O(nlogn)，最差情况为O(n²)，空间复杂度O(n)