[LeetCode] My Calendar I

leetcode

Very similar to insert intervals, too! 

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
class MyCalendar:

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


    def book(self, start, end):
        """
        :type start: int
        :type end: int
        :rtype: bool
        """
        find = False
        for i in range(len(self.schedule)):
            time = self.schedule[i]
            if start < time[1] and end > time[0]:
                return False
            if time[0] > start:
                self.schedule.insert(i, (start, end))
                find = True
                return True
        if not find:
            self.schedule.append((start, end))
        return True


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

If we want to improve time complexity, we can use binary search and a tree 

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
32
33
34
35
36
37
38
39
40
class Node:
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.left = self.right = None

class Tree:
    def __init__(self):
        self.root = None

    def insert_node(self, node, root):
        if not root:
            self.root = node
            return True

        if node.start >= root.end:
            if not root.right:
                root.right = node
                return True
            return self.insert_node(node, root.right)
        elif node.end <= root.start:
            if not root.left:
                root.left = node
                return True
            return self.insert_node(node, root.left)
        else:
            return False
class MyCalendar:

    def __init__(self):
        self.tree = Tree()

    def book(self, start, end):
        """
        :type start: int
        :type end: int
        :rtype: bool
        """
        node = Node(start, end)
        return self.tree.insert_node(node, self.tree.root)