0731. My Calendar II

题目信息

题号:

0731

难度:

Medium

主题:

设计、半开区间、重复预约

原题:

LeetCode 0731

重点:

允许同一时刻被两个日程覆盖,但不允许三个日程存在共同的非空交集;失败预约不得写入对象状态

题目重述

实现 MyCalendarTwo 类。新建对象时日历为空,每次通过 book(startTime, endTime) 尝试加入一个半开时间区间 [startTime, endTime)。

同一时刻被两个已接受日程覆盖属于合法的双重预约;若加入新日程后,会存在某段非空时间同时被三个日程覆盖,则形成三重预约,方法必须返回 false,并且不能保存该日程。否则返回 true 并将它加入日历。两个区间只在端点相接时没有非空交集,不算重叠。

每次调用满足 0 <= startTime < endTime <= 10^9,book 最多调用 1000 次。同一个对象必须在多次调用之间保留所有成功加入的日程。

自建示例

允许双重预约但拒绝三重预约:

输入:
操作 = ["MyCalendarTwo", "book", "book", "book", "book"]
参数 = [[], [2,8], [4,6], [5,7], [6,9]]
输出:[null, true, true, false, true]
解释:[2,8) 与 [4,6) 在 [4,6) 内形成双重预约,仍可接受;[5,7) 会使 [5,6) 同时被三个日程覆盖,因此被拒绝且不保存。随后 [6,9) 与 [4,6) 只在端点 6 相接,加入后最多仍是双重预约。

失败调用不会占用候选区间:

输入:
操作 = ["MyCalendarTwo", "book", "book", "book", "book"]
参数 = [[], [30,50], [40,60], [45,55], [50,55]]
输出:[null, true, true, false, true]
解释:前两个日程在 [40,50) 形成双重预约,所以 [45,55) 会在 [45,50) 造成三重预约并被拒绝。失败调用不保存;随后 [50,55) 只与 [40,60) 重叠,因此可以加入。