员工空闲时间怎么求？多个人的区间日程如何合并？

简化版

员工空闲时间可以先把所有人的工作区间摊平成一个列表，按开始时间排序后合并所有忙碌区间。相邻两个合并后忙碌区间之间的空隙，就是所有员工共同空闲时间。

详细版

每个员工的日程是一组不重叠且有序的忙碌区间。要求所有员工都空闲的时间，其实就是求“全体忙碌区间并集”的补集。最直接做法是把所有区间放到一个数组里，按 start 升序排序，然后像合并区间一样维护当前忙碌段 [curStart, curEnd]。

遍历新区间时，如果 next.start <= curEnd，说明忙碌时间重叠或相接，扩展 curEnd；如果 next.start > curEnd，说明 [curEnd, next.start] 是一个共同空闲段，然后开启新的忙碌段。

复杂度是 O(N log N)，N 是所有区间总数。也可以用最小堆做多路归并，复杂度 O(N log K)，K 是员工人数，更适合每个人日程已经有序且人数远小于总区间数的场景。

完整版教学

一、为什么先合并忙碌时间

题目问“所有员工都空闲”，直接找空闲不太方便，因为每个人的空闲是工作区间之间的无限补集。更简单的角度是：只要有任意员工在忙，这段时间就不是共同空闲。

因此先把所有人的忙碌区间求并集，再看并集之间的空隙。比如员工 A 忙 [1,3],[6,7]，员工 B 忙 [2,4]，全体忙碌并集是 [1,4],[6,7]，共同空闲就是 [4,6]。

记忆钩子：共同空闲不是先交空闲表，而是先并忙碌表，再取忙碌并集之间的缝。

二、摊平排序合并法

最直接的方法是把所有区间放进一个列表，然后按开始时间排序。排序后，所有可能重叠的忙碌区间都会相邻，合并逻辑就和 LeetCode 56 一样。

A: [1,3] [6,7]
B: [2,4]
C: [2,5] [9,12]

摊平排序: [1,3] [2,4] [2,5] [6,7] [9,12]
忙碌并集: [1,5] [6,7] [9,12]
共同空闲: [5,6] [7,9]

这里通常不输出负无穷到第一个忙碌段之前、最后一个忙碌段之后的空闲，因为题目只要求有限公共空闲区间。

三、代码模板

List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
    List<Interval> all = new ArrayList<>();
    for (List<Interval> person : schedule) {
        all.addAll(person);
    }
    all.sort((a, b) -> a.start - b.start);

    List<Interval> ans = new ArrayList<>();
    int curEnd = all.get(0).end;

    for (int i = 1; i < all.size(); i++) {
        Interval in = all.get(i);
        if (in.start > curEnd) {
            ans.add(new Interval(curEnd, in.start));
            curEnd = in.end;
        } else {
            curEnd = Math.max(curEnd, in.end);
        }
    }
    return ans;
}

如果区间端点可能很大，排序比较器也可以写成 Integer.compare(a.start, b.start)，避免 a.start - b.start 溢出。

四、多路归并优化

每个员工的日程本来就是有序的，可以用最小堆按当前区间 start 做 K 路归并。堆里每次弹出最早开始的区间，再把同一员工的下一个区间放入堆。

heap item = (interval.start, employeeId, indexInEmployeeSchedule)
每次弹出全局最早区间
用 curEnd 合并或产生空闲段
再推入该员工的下一个区间

如果总区间数 N 很大、员工数 K 较小，堆法是 O(N log K)，比整体排序 O(N log N) 更好。但代码复杂度更高，普通面试可以先写摊平排序法，再补充优化。

五、数字例子手推

输入：

员工	忙碌区间
A	`[1,2]`, `[5,6]`
B	`[1,3]`
C	`[4,10]`

排序后是 [1,2],[1,3],[4,10],[5,6]。合并前两个得到忙碌 [1,3]，下一个 [4,10] 与它断开，所以 [3,4] 是共同空闲；之后 [5,6] 被 [4,10] 覆盖，不产生新空闲。

六、端点相接要不要算空闲

情况	判断	是否产生空闲
`[1,3]` 和 `[3,5]`	`next.start == curEnd`	否
`[1,3]` 和 `[4,5]`	`next.start > curEnd`	是，`[3,4]`
`[1,5]` 和 `[2,3]`	覆盖	否

多数区间题默认半开区间或把端点相接视为无空隙，因此只有 next.start > curEnd 才产生空闲时间。用 >= 会错误地产生长度为 0 的空闲段。

七、常见误区与追问

误区：先求每个人空闲时间再做交集更简单。 空闲时间包含无限边界，处理更麻烦；合并忙碌区间更稳。
误区：相接区间也算空闲。 [3,3] 长度为 0，通常不作为空闲时间输出。
误区：只比较同一个员工内部区间。 共同空闲取决于所有员工的忙碌并集，必须跨员工合并。
追问：如何把 O(N log N) 优化到 O(N log K)？ 利用每个员工日程已排序，用最小堆做多路归并。
追问：为什么不输出最前和最后的无限空闲？ 题目通常要求有限空闲区间，无界区间没有明确端点。
追问：如果输入区间可能无序怎么办？ 要么先对每个人排序，要么整体摊平后统一排序。

八、加强记忆

员工空闲时间的主线是“忙碌并集的缝”。把所有忙碌区间按开始时间归并，合并出一段段全体忙碌覆盖；相邻忙碌段之间 curEnd < next.start 的空隙，就是共同空闲。普通写法用摊平排序，进阶写法用堆做多路归并。

简化版

详细版