Problem statement

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

Solution 1

There is O(n^2) solution with the following idea: let self.one be sorted list with intervals, which are visited once and self.two intervals visited twice. Then when we have new interval, we:

  1. Check if this interval have intersections with self.two list. If it has, we immediately return False.
  2. Next, we find place, where our interval is intersecting with self.one list. First of all, this interval is not intersecting with self.two, in opposite case we already should have returned False. So, we just need to insert in right place part of self.one list. Note also, that depending on parity of start and end, we either add it or not (see Problem 0715 Range Module for similar trick).
  3. Also, we need to fix self.one: remove all elements, which are now covered twice and again use trick with ends. \end{itemize}

Complexity

Overall time complexity is O(n^2), space complexity is O(n).

Code

class MyCalendarTwo:
    def __init__(self):
        self.one = []  # intervals that are booked once
        self.two = []  # intervals that are booked twice
        
    def book(self, start, end):
        if (t := bisect.bisect_right(self.two, start)) % 2: return False
        if t != bisect.bisect_left(self.two, end): return False
        
        i = bisect.bisect_right(self.one, start)
        j = bisect.bisect_left(self.one, end)
        
        self.two[t:t] = [start]*(i%2) + self.one[i:j] + [end]*(j%2)
        self.one[i:j] = [start]*((i+1)%2) + [end]*((j+1)%2)
                
        return True

Solution 2

There is also O(n log n) algorithm (which in practice works more or less the same): we use Sorted Lists instead of usual lists: then each element will be added and removed from each sorted list O(1) times (to check)

Complexity

It is O(n log n) for time and O(n) for space.

Code

from sortedcontainers import SortedList

class MyCalendarTwo:
    def __init__(self):
        self.one = SortedList()  # intervals that are booked once
        self.two = SortedList()  # intervals that are booked twice
        
    def book(self, start, end):
        if (t := SortedList.bisect_right(self.two, start)) % 2: return False
        if t != SortedList.bisect_left(self.two, end): return False
        
        i = SortedList.bisect_right(self.one, start)
        j = SortedList.bisect_left(self.one, end)
        
        for item in [start]*(i%2) + self.one[i:j] + [end]*(j%2): self.two.add(item)
        for _ in range(j-i): del self.one[i]
        for item in  [start]*((i+1)%2) + [end]*((j+1)%2): self.one.add(item)
                
        return True

Remark

Notice that there is also segment tree solution, where we use sparse segment tree with complexity O(n log M), where M = 10**9.