Hard

My Calendar III

LAB

After each half-open interval booking, return the maximum number of simultaneous active bookings so far.

EXAMPLES

Example 1

Input
{
  "bookings": [
    [
      10,
      20
    ],
    [
      50,
      60
    ],
    [
      10,
      40
    ],
    [
      5,
      15
    ],
    [
      5,
      10
    ],
    [
      25,
      55
    ]
  ]
}

Output
[
  1,
  1,
  2,
  3,
  3,
  3
]

FUNCTION SHAPE

bookings: intMatrix→intArray

SOLUTION NOTE

Unlike the previous problems, we accept all bookings and simply return the maximum number of concurrent events after each booking. This is a 'hard' problem, but I would classify it as an easy if you read this chapter :)

Reveal reference solution +

pythonREFERENCE

from sortedcontainers import SortedDict

class MyCalendarThree:
    def __init__(self):
        self.lines = SortedDict()

    def book(self, start, end):
        curr_sum = 0
        if start not in self.lines: self.lines[start] = 0
        if end not in self.lines: self.lines[end] = 0

        self.lines[start] += 1
        self.lines[end] -= 1

        res = 0
        for time in self.lines:
            curr_sum += self.lines[time]
            res = max(res, curr_sum)

        return res

TimeO(n)

SpaceO(n)

Open on LeetCode ↗