题目重点：用 10080 分钟半开区间统一 allowed/freeze，再转换时区并筛最早可部署、最短持续时间和前 k 个窗口。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 输入每条本地窗口先满足 0≤start<end≤10080；跨周仅可能由时区平移产生。训练版将跨周转换后的窗口拆为本周 [0,10080) 内两段。
- Part 2 的 utc_now 为当前周内分钟，训练版只返回本周余下窗口；若题目要求跨未来多周，需把周期窗口展开到绝对时间线，不能按本周截断。
- lead_time、min_continuous_minutes、k 非负；在 utc_now+lead 之前的窗口被截去左边，截后长度再和 minimum 比。相邻结果合并为一段。
解题路线
- 把 allowed 与 freeze 各做区间并集；可用 sweep line 在每个端点维护两类 active count，只有 allowed>0 且 freeze=0 的片段可部署。半开区间使某段的 end 与下一段 start 接触时没有重叠或一分空隙。
- 时区 offset 的符号采用 UTC=local−offset；转换后先 modulo 10080，再把超过周末的段切成 [start,10080) 与 [0,end−10080)。不能只对两个端点各自取模然后当作 start<end。
- 在最终 UTC 窗口上与 [utc_now+lead,10080) 求交，再丢弃短于 minimum 的连续段，按起点升序取前 k 个。若业务想要可开始时刻而非整个可用区间，输出合同需改。
- 训练代码利用一周只有 10080 分钟，使用两组差分数组逐分钟扫描，天然合并相邻分钟；更大时间域改为端点排序 O(n log n)。
- 测试 freeze 完全覆盖、两个 allowed 相邻、两个 freeze 重叠、跨周折返、threshold 落段中、最短长度恰边界、k=0 以及允许/冻结同点开始结束。
手动走一遍
题目样例 allowed [540,600)、freeze [570,585) 得 [540,570)、[585,600)。时区例 offset=-480，local allowed [540,600) 变 UTC [1020,1080)，freeze [550,565) 变 [1030,1045)，utc_now=1020、lead=0、minimum=10 时返回 [1020,1030) 和 [1045,1080)。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from __future__ import annotations
WEEK = 7 * 24 * 60
def _utc_segments(start: int, end: int, offset: int) -> list[tuple[int, int]]:
if not 0 <= start < end <= WEEK:
raise ValueError("expected a nonempty local half-open interval in one week")
first = (start - offset) % WEEK
length = end - start
if first + length <= WEEK:
return [(first, first + length)]
return [(first, WEEK), (0, first + length - WEEK)]
def deployment_windows(
rules: list[tuple[int, int, str, int]],
*,
utc_now: int = 0,
lead_minutes: int = 0,
min_duration: int = 1,
limit: int | None = None,
) -> list[tuple[int, int]]:
"""Training contract: return windows only in the current UTC week.
Rule is (local_start, local_end, 'allowed'|'freeze', utc_offset_minutes).
Part 1 uses offset 0 and defaults for the other arguments.
"""
if lead_minutes < 0 or min_duration < 0 or (limit is not None and limit < 0):
raise ValueError("lead, minimum duration and limit must be nonnegative")
if limit == 0:
return []
allowed_diff = [0] * (WEEK + 1)
freeze_diff = [0] * (WEEK + 1)
for start, end, kind, offset in rules:
if kind not in ("allowed", "freeze"):
raise ValueError("rule kind must be allowed or freeze")
diff = allowed_diff if kind == "allowed" else freeze_diff
for lo, hi in _utc_segments(start, end, offset):
diff[lo] += 1
diff[hi] -= 1
earliest = max(0, utc_now + lead_minutes)
active_allowed = active_freeze = 0
start = None
answer: list[tuple[int, int]] = []
for minute in range(WEEK + 1):
active_allowed += allowed_diff[minute]
active_freeze += freeze_diff[minute]
usable = minute < WEEK and minute >= earliest and active_allowed > 0 and active_freeze == 0
if usable and start is None:
start = minute
elif not usable and start is not None:
if minute - start >= min_duration:
answer.append((start, minute))
if limit is not None and len(answer) >= limit:
return answer
start = None
return answer
复杂度
训练版固定周长 W=10080、R 条规则，区间拆分与标记 O(R)，扫描 O(W)，空间 O(W)；通用端点 sweep O(R log R) 时间、O(R) 空间。跨周扩展到 H 周会增加 O(HR) 个周期实例或按周期查询。
易错点与追问
容易失分的边界
- 使用闭区间把 end 那一分钟也算可部署。
- 时区 offset=-480 时写成 UTC=local−480，方向相反。
- 只对 start/end 各取模，不拆跨周窗口。
- 先按最短长度过滤再剪掉 lead 前半段，留下实际不足时长的窗口。
- 把‘接下来 k’擅自解释为无限重复周而不注明训练边界。
继续深挖
- 如果 utc_now=周日且最早时刻落下周，如何用绝对 UTC 时间展开周期窗口？
- 多地时区有 DST 变化时固定 offset 还能代表当地周吗？
- 动态增加/删除 allowed 和 freeze，如何维护可部署段？
