[LeetCode] My Calendar I

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)