SWE · System Design / 设计追问

日历免打扰空闲区间:统一时区、裁剪窗口和取补集

给定忙碌/免打扰区间,列出查询窗口内全部可用时段。

题目重点:给定忙碌/免打扰区间,列出查询窗口内全部可用时段。

题意与假设

这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。

  • 明确训练合同:所有busy都不可用,查询窗口[H0,H1),输出全部空闲半开区间;多人场景取全部busy的并集。
  • 输入已转为同一时间轴;重复日历事件先在指定时区展开,跨DST不能简单加固定24小时。

解题路线

  1. 先过滤与查询窗无交集的区间,再裁剪端点到窗内。排序合并busy,使重叠和接触片段成为一段。
  2. cursor从H0开始;每段busy的起点大于cursor时输出[cursor,start),再推进cursor=max(cursor,end);末尾补[cursor,H1)。
  3. 把展示时区与内部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频繁且查询窗口变化,怎样使用区间树与缓存失效?
✓已复制微信号!