LC 729

Solution to LeetCode 729 My calendar I. It uses “range-based query“, which is similar to LeetCode 715, LeetCode 699, LeetCode 56 and LeetCode 57.

LeetCode 729

My calendar I (Medium). [link]

1. Brute Force

   There are four cases of overlapping, and can be determined by min(start1. start2) < min(end1, end2).

   Time complexity O(n^2), space complexity O(n).

class MyCalendar(object):

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

    def book(self, start, end):
        """
        :type start: int
        :type end: int
        :rtype: bool
        """
        for s, e in self.calendar:
            if max(s, start) < min(e, end): # consider 4 conditions of overlapping
                return False
        self.calendar.append((start, end))
        return True

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

2. Binary Search

   Time complexity O(n log n), space complexity O(n).

class Node(object):

    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.left = self.right = None

    def insert(self, node):
        """
        :type start: int
        :type end: int
        :rtype: bool
        """
        if node.start >= self.end: # no overlap
            if not self.right:
                self.right = node
                return True
            return self.right.insert(node) # search the right
        elif node.end <= self.start: # no overlap
            if not self.left:
                self.left = node
                return True
            return self.left.insert(node) # search the left
        else:
            return False
        
class MyCalendar(object):
    
    def __init__(self):
        self.root = None
        
    def book(self, start, end):
        if not self.root:
            self.root = Node(start, end)
            return True
        return self.root.insert(Node(start, end))

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