731. My Calendar II

Problem

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a triple booking.

A triple booking happens when three events have some non-empty intersection (i.e., some moment is common to all the three events.).

The event can be represented as a pair of integers startTime and endTime that represents a booking on the half-open interval [startTime, endTime), the range of real numbers x such that startTime <= x < endTime.

Implement the MyCalendarTwo class:

MyCalendarTwo() Initializes the calendar object.
boolean book(int startTime, int endTime) Returns true if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return false and do not add the event to the calendar.

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

Example 1:

Input
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, true, true, true, false, true, true]
Explanation

MyCalendarTwo myCalendarTwo = new MyCalendarTwo();
myCalendarTwo.book(10, 20); // return True, The event can be booked.
myCalendarTwo.book(50, 60); // return True, The event can be booked.
myCalendarTwo.book(10, 40); // return True, The event can be double booked.
myCalendarTwo.book(5, 15);  // return False, The event cannot be booked, because it would result in a triple booking.
myCalendarTwo.book(5, 10); // return True, The event can be booked, as it does not use time 10 which is already double booked.
myCalendarTwo.book(25, 55); // return True, The event can be booked, as the time in [25, 40) will be double booked with the third event, the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.

Constraints:

0 <= start < end <= 10⁹
At most 1000 calls will be made to book.

Test Cases

class MyCalendarTwo:

    def __init__(self):


    def book(self, startTime: int, endTime: int) -> bool:



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

solution_test.py

import pytest

from solution import MyCalendarTwo

null = None
false = False
true = True


@pytest.mark.parametrize('actions, params, expects', [
    (
        ["MyCalendarTwo", "book", "book", "book", "book", "book", "book"],
        [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]],
        [null, true, true, true, false, true, true],
    ),

    (
        ["MyCalendarTwo","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book","book"],
        [[],[89,100],[30,43],[92,100],[31,49],[59,76],[60,73],[31,49],[80,99],[48,60],[36,52],[67,82],[96,100],[22,35],[18,32],[9,24],[11,27],[94,100],[12,22],[61,74],[3,20],[14,28],[27,37],[5,20],[1,11],[96,100],[33,44],[90,100],[40,54],[23,35],[18,32],[78,89],[56,66],[83,93],[45,59],[40,59],[94,100],[99,100],[86,96],[43,61],[29,45],[21,36],[13,31],[17,30],[16,30],[80,94],[38,50],[15,30],[62,79],[25,39],[73,85],[39,56],[80,97],[42,57],[32,47],[59,78],[35,53],[56,74],[75,85],[39,54],[63,82]],
        [null,true,true,true,true,true,true,false,false,true,false,false,false,false,false,true,true,false,false,false,false,false,false,false,true,false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,false,true,false,false,false,false,false,false,false,false,false,false],
    )
])
@pytest.mark.parametrize('clazz', [MyCalendarTwo])
def test_solution(clazz, actions, params, expects):
    sol = None
    for action, args, expected in zip(actions, params, expects):
        if action == 'MyCalendarTwo':
            sol = clazz(*args)
        else:
            assert getattr(sol, action)(*args) == expected

Thoughts

729. My Calendar I 的进阶版，从任意两个 events 不能有重叠，扩展为三个 events 不能有共同的交集。

如果已经知道所有同时被两个 events 占用的时段，就可以像 729. My Calendar I 那样直接判断一个新的 event，是否跟某个时段有重叠，有的话就无法预订。

按这个思路，维护两个有序数组，single_occupies 记录所有被至少一个 event 占用的时段，double_occupies 记录所有被两个 events 同时占用的时段，都按照时段的开始时间排序，且任意两个时段之间没有重叠。

对于想要 book 的一个 event，对 double_occupies 用二分搜索找到可以插入的位置（如 i），检查 double_occupies[i-1] 的结束时间是否在 event 之前，double_occupies[i] 的开始时间是否在 event 之后。如果都符合，则此 event 可以预订成功，否则直接返回 false。这个逻辑跟 729. My Calendar I 一样。

为了简化边界的处理，可以给 single_occupies 和 double_occupies 的两头分别加一个 (-inf, -inf) 和 (inf, inf) 做占位符。

麻烦在于维护 single_occupies 和 double_occupies 这两个数组。

首先用二分搜索在 single_occupies 中找到可以插入的位置，从这个位置开始，找到新 event 会覆盖到的所有后续时段，一方面需要把每个时段与新 event 的交集加入到 double_occupies（因为这些交集部分同时被两个 events 占用），另一方面需要将所有这些时段合并为一个（以便以后使用）。

实操的时候需要注意新 event 的两个端点处，可能会跟 single_occupies 中的时段部分重叠，而中间的部分会完全覆盖 single_occupies 中的对应时段。

被边界情况搞到吐血。所幸提交后 runtime beats 100%。

MyCalendarTwo 构造的时间复杂度 O(1)。

book 方法，判定能否预订的时间复杂度 O(log n)，执行预订的时间复杂度 O(n)。

空间复杂度 O(n)。

Code

solution.py

from bisect import bisect_left
from math import inf


Range = tuple[int, int]
min2 = lambda a, b: a if a <= b else b
max2 = lambda a, b: a if a >= b else b


class MyCalendarTwo:

    def __init__(self):
        self._single_occupies: list[Range] = [(-inf, -inf), (inf, inf)]
        self._double_occupies: list[Range] = [(-inf, -inf), (inf, inf)]

    def book(self, startTime: int, endTime: int) -> bool:
        i = bisect_left(self._double_occupies, (startTime, endTime))
        if self._double_occupies[i-1][1] > startTime or self._double_occupies[i][0] < endTime:
            return False

        new_doubles = []
        j = bisect_left(self._single_occupies, (startTime, endTime))
        jl = j
        if self._single_occupies[jl-1][1] > startTime:
            jl -= 1
            new_doubles.append((
                startTime,
                min2(self._single_occupies[jl][1], endTime),
            ))
        while self._single_occupies[j][0] < endTime:
            new_doubles.append((
                self._single_occupies[j][0],
                min2(self._single_occupies[j][1], endTime),
            ))
            j += 1
        self._single_occupies[jl:j] = [(
            min2(self._single_occupies[jl][0], startTime),
            max2(self._single_occupies[j-1][1], endTime),
        )]

        self._double_occupies[i:i] = new_doubles
        return True


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