Medium

My Calendar II

LAB

Simulate bookings allowing double bookings but rejecting any booking that would create a triple booking.

EXAMPLES

Example 1

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

Output
[
  true,
  true,
  true,
  false,
  true,
  true
]

FUNCTION SHAPE

bookings: intMatrix→boolArray

SOLUTION NOTE

This is similar to MyCalendar I, but now we allow the active count to reach 2 (double booking) but not 3 (triple booking). We only need to change 1 number! This is the power of template/generic based solutions. Understand 1 concept to solve many problems.

Reveal reference solution +

pythonREFERENCE

from sortedcontainers import SortedDict

class MyCalendarTwo:
    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

        for time in self.lines:
            curr_sum += self.lines[time]
            if curr_sum == 3:  # ONLY CHANGE THIS FROM 2 TO 3
                self.lines[start] -= 1
                self.lines[end] += 1
                if self.lines[start] == 0: del self.lines[start]
                if self.lines[end] == 0: del self.lines[end]
                return False

        return True

TimeO(n)

SpaceO(n)

Open on LeetCode ↗