LC-0732 Hard LeetCode

732. My Calendar III

Binary Search Design Segment Tree Prefix Sum Ordered Set

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 71% Topics: Binary Search, Design, Segment Tree, Prefix Sum, Ordered Set

Reading material

Binary Search 12 min Design (Data Structures) 14 min Segment & Fenwick Trees 16 min

Reference solution (spoiler · python)

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

import bisect


class MyCalendarThree(object):

    def __init__(self):
        self.__books = [[-1, 0]]
        self.__count = 0

    def book(self, start, end):
        """
        :type start: int
        :type end: int
        :rtype: int
        """
        i = bisect.bisect_right(self.__books, [start, float("inf")])
        if self.__books[i-1][0] == start:
            i -= 1
        else:
            self.__books.insert(i, [start, self.__books[i-1][1]])
        j = bisect.bisect_right(self.__books, [end, float("inf")])
        if self.__books[j-1][0] == end:
            j -= 1
        else:
            self.__books.insert(j, [end, self.__books[j-1][1]])            
        for k in xrange(i, j):
            self.__books[k][1] += 1
            self.__count = max(self.__count, self.__books[k][1])
        return self.__count


# Time:  O(n^2)
# Space: O(n)
class MyCalendarThree2(object):

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


    def book(self, start, end):
        """
        :type start: int
        :type end: int
        :rtype: int
        """
        i = bisect.bisect_left(self.__books, (start, 1))
        if i < len(self.__books) and self.__books[i][0] == start:
            self.__books[i] = (self.__books[i][0], self.__books[i][1]+1)
        else:
            self.__books.insert(i, (start, 1))

        j = bisect.bisect_left(self.__books, (end, 1))
        if j < len(self.__books) and self.__books[j][0] == end:
            self.__books[j] = (self.__books[j][0], self.__books[j][1]-1)
        else:
            self.__books.insert(j, (end, -1))

        result, cnt = 0, 0
        for book in self.__books:
            cnt += book[1]
            result = max(result, cnt)
        return result

Solution from kamyu104/LeetCode-Solutions · MIT