Meta 所有员工共同空闲：忙碌并集的有限空隙

题意与假设

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

• 训练busy半开[start,end)，每段正长度，输出全部人的共同空闲有限区间；未给工作horizon，不输出负无穷到首busy或末busy到正无穷。
• 某人无busy不影响别人忙碌并集，所有schedule都空时[]表示没有可表示的有限horizon，不意味着实际无人空闲。

解题路线

1. 一个时刻所有人空闲，当且仅当没有任何人的busy覆盖，即全busy并集的补集。无需逐对员工交集，先flatten区间排序。
2. 按start排序，维护当前并集end；新start>end出现有限gap(end,start)，再更新end=max(end,finish)。start=end仅接触没有正长度空闲。
3. 重叠、嵌套与不同员工相同区间都由并集处理。若每员工已排序，可用k路heap流式合并减少全sort，但仍需消费全部busy。
4. 业务若给[horizonStart,horizonEnd)，需要裁剪busy并增加两端空隙，合同不同；不能默默丢工作日早晚空闲后声称完整时间范围。

手动走一遍

员工A忙[1,3],[6,7]，B忙[2,4]，并集[1,4],[6,7]，共同有限空闲[4,6]。忙[1,2]与[2,3]无正长度gap。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def common_free_time(schedules):
    """Busy half-open intervals [start,end), finite gaps only; no common horizon.
    Empty schedules/one employee never-busy give no unbounded intervals output.
    """
    intervals=[interval for schedule in schedules for interval in schedule]
    if any(start>=end for start,end in intervals):raise ValueError('positive interval')
    if not intervals:return []
    intervals.sort();end=intervals[0][1];result=[]
    for start,finish in intervals[1:]:
        if start>end:result.append((end,start))
        end=max(end,finish)
    return result

复杂度

K总busy段，O(K logK)排序/O(K)flatten空间，gap输出O(K)。每人已排序的k路版本O(K log员工数)、heap O(员工数)加输出。

易错点与追问

容易失分的边界

• 把各人的忙碌交集当共同空闲，逻辑反了。
• 无horizon却擅自生成0点到首busy区间。

继续深挖

• 需要任何至少m人空闲时，改扫描人数计数而不是简单并集。
• 端点闭合时空闲区间边界表示需要怎样改变？