LC-0731 Medium LeetCode

731. My Calendar II

Array Binary Search Design Segment Tree Prefix Sum Ordered Set

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 62% Topics: Array, Binary Search, Design, Segment Tree, Prefix Sum, Ordered Set

Reading material

Arrays & Hashing 12 min Binary Search 12 min Design (Data Structures) 14 min

Reference solution (spoiler · python)

# Time:  O(n^2)
# Space: O(n)

class MyCalendarTwo(object):

    def __init__(self):
        self.__overlaps = []
        self.__calendar = []


    def book(self, start, end):
        """
        :type start: int
        :type end: int
        :rtype: bool
        """
        for i, j in self.__overlaps:
            if start < j and end > i:
                return False
        for i, j in self.__calendar:
            if start < j and end > i:
                self.__overlaps.append((max(start, i), min(end, j)))
        self.__calendar.append((start, end))
        return True

Solution from kamyu104/LeetCode-Solutions · MIT