题目重点:给定忙碌/免打扰区间,列出查询窗口内全部可用时段。
题意与假设
这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。
- 明确训练合同:所有busy都不可用,查询窗口[H0,H1),输出全部空闲半开区间;多人场景取全部busy的并集。
- 输入已转为同一时间轴;重复日历事件先在指定时区展开,跨DST不能简单加固定24小时。
解题路线
- 先过滤与查询窗无交集的区间,再裁剪端点到窗内。排序合并busy,使重叠和接触片段成为一段。
- cursor从H0开始;每段busy的起点大于cursor时输出[cursor,start),再推进cursor=max(cursor,end);末尾补[cursor,H1)。
- 把展示时区与内部UTC瞬间分开。若请求每人至少m分钟共同空闲,先求补集再按长度筛,不先独立筛每人的短段。
手动走一遍
窗口[9,18),busy[8,10)、[12,13)、[12.5,15)、[18,20):裁剪合并后[9,10)、[12,15),free为[10,12)、[15,18)。若无busy则整个窗口可用;busy完整覆盖窗口则输出空。
规模与取舍
n区间排序O(nlogn)、扫描O(n),空间O(n)含裁剪/结果。多日事件展开成本按实例数计,而非日历规则数。
易错点与追问
容易失分的边界
- 缺少有限查询窗口时无法完整表示左右无穷空闲。
- 半开区间在busy结束瞬间可预约;含端点合同会改变接触语义。
继续深挖
- 若只有k个参加者中的至少r人需要出席,应怎样扫参与人数而不是取全busy并集?
- 新增busy频繁且查询窗口变化,怎样使用区间树与缓存失效?
