Problem statement

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

Solution 1

The idea is to use idea of cumulative sum: instead of booking [a, b] segment, we add 1 to points[a] and remove 1 from points[b] (see this trick in 0253 Meeting Rooms II problem).

Complexity

Time complexity of this approach is O(n^2*log n), because we need to sort data n times.

Code

class MyCalendarThree:
    def __init__(self):
        self.points = Counter()
        
    def book(self, start, end):
        self.points[start] += 1
        self.points[end] -= 1
        return max(accumulate(i for _, i in sorted(self.points.items())))

Solution 2

There is also segment tree solution with O(n log N) solution, where N is the biggest value of numbers in intervals. The idea is to use sparse segment tree with lazy updates (see Segment tree pattern). After we use it code is pretty easy: we just need to update segment and then return query for each new point.

Complexity

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

Code

class SegmentTree:
    def __init__(self, N, update_fn, query_fn):
        self.UF, self.QF = update_fn, query_fn
        self.T = defaultdict(int)   # [0] * (4*N)
        self.L = defaultdict(int)   # [0] * (4*N)
    
    def push(self, v):
        for u in [2*v, 2*v+1]:
            self.T[u] = self.UF(self.T[u], self.L[v])
            self.L[u] = self.UF(self.L[u], self.L[v])
        self.L[v] = 0

    def update(self, v, tl, tr, l, r, h):
        if l > r: return
        if l == tl and r == tr:
            self.T[v] = self.UF(self.T[v], h)
            self.L[v] = self.UF(self.L[v], h)
        else:
            self.push(v)
            tm = (tl + tr)//2
            self.update(v*2, tl, tm, l, min(r, tm), h)
            self.update(v*2+1, tm+1, tr, max(l, tm+1), r, h)
            self.T[v] = self.QF(self.T[v*2], self.T[v*2+1])

    def query(self, v, tl, tr, l, r):
        if l > r: return -float("inf")
        if l <= tl and tr <= r: return self.T[v]
        self.push(v)
        tm = (tl + tr)//2
        return self.QF(self.query(v*2, tl, tm, l, min(r, tm)), self.query(v*2+1, tm+1, tr, max(l, tm+1), r))


class MyCalendarThree:
    def __init__(self):
        self.N = N = 10**9 + 1
        self.STree = SegmentTree(N, lambda a,b: a+b, max)
        
    def book(self, start, end):
        self.STree.update(1, 0, self.N-1, start + 1, end, 1)
        return self.STree.query(1, 0, self.N-1, 1, 10**9)

Solution 3

There is also O(n^2) solution, similar to the first solution, where we do not sort our data each time, but keep it sorted and insert elements in O(n). Note, that this solution can be optimized, we do not need to iterate over all lst, but we can find places i and j where we insert our new segment and then look only on [i, j] interval. Complexity will be the same, but in practice it will work like 5 times faster.

Complexity

It is O(n^2) for time and O(n) for space.

Code

class MyCalendarThree:
    def __init__(self):
        self.lst = []

    def book(self, start, end):
        bisect.insort(self.lst, (start, 1))
        bisect.insort(self.lst, (end, -1))
        k, tmp = 0, 0
        for t, n in self.lst:
            tmp += n
            k = max(k, tmp)
        return k

Remark

Open question, if there is O(n log n) solution.