732. My Calendar III

Problem

A k-booking happens when k events have some non-empty intersection (i.e., there is some time that is common to all k events.)

You are given some events [startTime, endTime), after each given event, return an integer k representing the maximum k-booking between all the previous events.

Implement the MyCalendarThree class:

MyCalendarThree() Initializes the object.
int book(int startTime, int endTime) Returns an integer k representing the largest integer such that there exists a k-booking in the calendar.

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

Example 1:

Input
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
Output
[null, 1, 1, 2, 3, 3, 3]
Explanation
1
2
3
4
5
6
7
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // return 1
myCalendarThree.book(50, 60); // return 1
myCalendarThree.book(10, 40); // return 2
myCalendarThree.book(5, 15); // return 3
myCalendarThree.book(5, 10); // return 3
myCalendarThree.book(25, 55); // return 3

Constraints:

0 <= startTime < endTime <= 10⁹
At most 400 calls will be made to book.

Test Cases

class MyCalendarThree:

    def __init__(self):


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



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

solution_test.py

import pytest

from solution import MyCalendarThree
from solution_omg import MyCalendarThree as MyCalendarThreeOmg

null = None


@pytest.mark.parametrize('actions, params, expects', [
    (
        ["MyCalendarThree", "book", "book", "book", "book", "book", "book"],
        [[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]],
        [null, 1, 1, 2, 3, 3, 3],
    ),

    (
        ["MyCalendarThree","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","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","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","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","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","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","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"],
        [[],[21,22],[86,87],[71,72],[76,77],[50,51],[92,93],[99,100],[5,6],[71,72],[42,43],[72,73],[22,23],[51,52],[15,16],[70,71],[64,65],[57,58],[47,48],[4,5],[14,15],[2,3],[28,29],[35,36],[86,87],[72,73],[99,100],[50,51],[25,26],[8,9],[69,70],[37,38],[55,56],[0,1],[20,21],[21,22],[96,97],[88,89],[40,41],[20,21],[94,95],[99,100],[19,20],[41,42],[0,1],[47,48],[51,52],[62,63],[32,33],[83,84],[39,40],[70,71],[36,37],[16,17],[63,64],[32,33],[35,36],[57,58],[68,69],[24,25],[73,74],[94,95],[32,33],[36,37],[21,22],[47,48],[54,55],[61,62],[67,68],[89,90],[57,58],[65,66],[23,24],[85,86],[79,80],[66,67],[2,3],[83,84],[46,47],[58,59],[69,70],[15,16],[89,90],[48,49],[93,94],[28,29],[22,23],[53,54],[50,51],[19,20],[1,2],[53,54],[70,71],[44,45],[36,37],[85,86],[4,5],[10,11],[14,15],[81,82],[9,10],[88,89],[21,22],[57,58],[91,92],[35,36],[77,78],[95,96],[39,40],[92,93],[43,44],[10,11],[73,74],[84,85],[42,43],[58,59],[22,23],[73,74],[85,86],[47,48],[68,69],[43,44],[94,95],[95,96],[31,32],[18,19],[35,36],[55,56],[54,55],[53,54],[28,29],[16,17],[42,43],[23,24],[22,23],[5,6],[69,70],[25,26],[9,10],[69,70],[55,56],[0,1],[33,34],[8,9],[91,92],[97,98],[42,43],[69,70],[50,51],[86,87],[63,64],[31,32],[55,56],[17,18],[26,27],[16,17],[10,11],[66,67],[90,91],[83,84],[52,53],[77,78],[3,4],[13,14],[7,8],[82,83],[85,86],[72,73],[82,83],[28,29],[98,99],[1,2],[92,93],[83,84],[52,53],[24,25],[6,7],[20,21],[56,57],[59,60],[29,30],[51,52],[37,38],[42,43],[40,41],[35,36],[36,37],[1,2],[50,51],[67,68],[57,58],[49,50],[22,23],[41,42],[49,50],[38,39],[37,38],[9,10],[87,88],[11,12],[47,48],[44,45],[85,86],[32,33],[64,65],[63,64],[24,25],[28,29],[88,89],[59,60],[90,91],[12,13],[90,91],[60,61],[38,39],[72,73],[45,46],[5,6],[70,71],[4,5],[53,54],[57,58],[29,30],[43,44],[95,96],[75,76],[10,11],[22,23],[35,36],[62,63],[74,75],[21,22],[54,55],[84,85],[49,50],[25,26],[78,79],[85,86],[54,55],[89,90],[48,49],[43,44],[83,84],[28,29],[55,56],[87,88],[56,57],[11,12],[40,41],[69,70],[0,1],[44,45],[20,21],[57,58],[32,33],[60,61],[82,83],[45,46],[54,55],[71,72],[43,44],[65,66],[31,32],[59,60],[12,13],[16,17],[71,72],[24,25],[1,2],[70,71],[91,92],[28,29],[11,12],[27,28],[48,49],[46,47],[16,17],[17,18],[75,76],[70,71],[31,32],[14,15],[74,75],[32,33],[9,10],[47,48],[24,25],[61,62],[51,52],[30,31],[86,87],[56,57],[31,32],[11,12],[65,66],[57,58],[28,29],[96,97],[81,82],[97,98],[48,49],[44,45],[8,9],[17,18],[31,32],[72,73],[95,96],[64,65],[85,86],[3,4],[67,68],[5,6],[81,82],[69,70],[67,68],[36,37],[6,7],[33,34],[20,21],[83,84],[70,71],[94,95],[25,26],[49,50],[4,5],[25,26],[64,65],[73,74],[63,64],[5,6],[14,15],[5,6],[72,73],[54,55],[73,74],[71,72],[46,47],[31,32],[80,81],[33,34],[4,5],[61,62],[19,20],[99,100],[30,31],[74,75],[79,80],[13,14],[23,24],[57,58],[82,83],[96,97],[36,37],[17,18],[29,30],[32,33],[70,71],[29,30],[10,11],[45,46],[99,100],[23,24],[57,58],[67,68],[80,81],[50,51],[96,97],[50,51],[76,77],[74,75],[5,6],[42,43],[64,65],[65,66],[52,53],[75,76],[12,13],[30,31],[66,67],[47,48],[27,28],[99,100],[80,81],[52,53],[37,38],[65,66],[78,79],[40,41],[11,12],[91,92],[29,30],[50,51],[96,97],[43,44],[94,95],[26,27],[98,99],[3,4],[40,41],[53,54]],
        [null,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9,9,9,9,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10],
    ),
])
@pytest.mark.parametrize('clazz', [MyCalendarThree, MyCalendarThreeOmg])
def test_solution(clazz, actions, params, expects):
    sol = None
    for action, args, expected in zip(actions, params, expects):
        if action == 'MyCalendarThree':
            sol = clazz(*args)
        else:
            assert getattr(sol, action)(*args) == expected

Thoughts

系列问题：

729. My Calendar I 任何时刻不能有两个 events
731. My Calendar II 任何时刻不能有三个 events

本题不再做限制，但是要能知道重叠的 events 的最大数量。

考虑记录每一个时间段的 events 个数。当两个 events 有重叠的时候，需要根据重叠的情况拆分成几个小的时间段，记录每个片段的 events 数量。

实现起来很麻烦，即便两头加了 -inf 和 inf 避免越界，仍然有各种边界情况需要处理，到处都是边界值刺客。而且运行时间很长（常数系数太大）。

solution_omg.py

虽然 AC 了，但不确定会不会在某些边缘 case 下会出错。

实际上大的区间被不断打散，经常会出现连续的多个区间在时间上也是相连的，与其以区间的形式一个一个记录，不如直接记录所有的分界点。对于一个时间段 [start, end)，可以记录成 [(start, 1), (end, 0)]，表示从 start 开始的每个时刻都有一个 event，从 end 开始的每个时刻则没有 event。如果另一个时间段 [start2, end2) 跟它有重叠，比如 start < start2 < end < end2，记录数组就可以改为 [(start, 1), (start2, 2), (end, 1), (end2, 0)]，说明时间段 [start2, end) 内有两个 events，end2 开始的时刻都没有 event，而 [start, start2) 和 [end, end2) 时段都各有一个 event。

可以在数组两头分别加上 (-inf, 0) 和 (inf, 0) 以简化边界处理。

对于一个待添加的时间段 [start, end)，用二分搜索分别找到 start 和 end 的插入位置（记为 i 和 j）。易知从 i（包含）到 j（不含）的每一个时间分界点，从其开始的每个时刻都多了一个 event （待添加的这个）。只需要注意 start 和 end 是不是原本已经存在并做好相应的更新。

注意 Python 自带的 bisect.bisect_left 的返回值（比如记作 i），有 ∀arr[:i] < x，∀arr[i:] ≥ x（在数组 arr 中二分查找 x 的插入位置）。

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

book 方法的时间复杂度最坏是 O(n)。

空间复杂度 O(n)。

提交后运行速度是上边时间段方法的 200 倍，runtime beats 100%。

Code

solution.py

from bisect import bisect_left
from math import inf


max2 = lambda a, b: a if a >= b else b


class MyCalendarThree:

    def __init__(self):
        self._occupies: list[list[int]] = [[-inf, 0], [inf, 0]] # [time, occupied events count]
        self._max_occupy = 0

    def book(self, startTime: int, endTime: int) -> int:
        i = bisect_left(self._occupies, [startTime])
        j = bisect_left(self._occupies, [endTime])
        if endTime < self._occupies[j][0]:
            self._occupies.insert(j, [endTime, self._occupies[j-1][1]])
        for k in range(i, j):
            self._occupies[k][1] += 1
        if startTime < self._occupies[i][0]:
            self._occupies.insert(i, [startTime, self._occupies[i-1][1] + 1])

        self._max_occupy = max2(self._max_occupy, max(self._occupies[k][1] for k in range(i, j + 1)))
        return self._max_occupy


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

本文引用
- 729. My Calendar I
- 731. My Calendar II

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。