Leetcode 731 Solution

This article provides solution to leetcode question 731 (my-calendar-ii)
Categories:
Tags:
Access this page by simply typing in "lcs 731" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/my-calendar-ii

Solution

class MyCalendarTwo:

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

    def search_pos(self, loc, flag):
        l = 0
        r = len(self.books) - 1
        while l < r:
            m = (l + r) // 2
            if self.books[m] >= (loc, flag):
                r = m
            else:
                l = m + 1
        return l if self.books and self.books[l] >= (loc, flag) else len(self.books)

    def book(self, start: int, end: int) -> bool:
        start_pos = self.search_pos(start, 1)
        self.books.insert(start_pos, (start, 1))

        end_pos = self.search_pos(end, -1)
        self.books.insert(end_pos, (end, -1))

        cur = 0
        for i, flag in self.books:
            cur += flag
            if cur > 2:
                start_pos = self.search_pos(start, 1)
                del self.books[start_pos]

                end_pos = self.search_pos(end, -1)
                del self.books[end_pos]

                return False

        return True

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