LeetCode 759. 员工空闲时间

2022-04-06 HGNULB 约 13 分钟

文章信息 7 个分类 4 个标签

分类

题目描述

✅ 759. 员工空闲时间

题意分析

给若干名员工的日程，每名员工的日程是一组互不重叠且已按时间升序排列的忙碌区间。求所有员工共同空闲的时间段——即在这段时间里每一个人都不忙——并按升序返回这些区间。

要什么：一组区间。注意「共同空闲」的定义是对全体员工取交集的空闲，等价于对全体忙碌区间取并集之后剩下的空隙。这两种表述等价，但后者好做得多：求 $k$ 个集合的交集要逐个求交，而把所有忙碌区间倒进一个池子里求并集，只需要一次排序加一次线性扫描。识别出这个转换，是这道困难题最核心的一步。

题面还有两条隐含约束必须抠清楚。第一，返回的空闲区间必须是有限长度且非零——两段忙碌区间首尾相接（前一段在 3 结束、后一段在 3 开始）时，中间没有任何可用时间，不能产出一个 [3,3] 的空区间。第二，第一段忙碌之前和最后一段忙碌之后都是无限长的空闲，题目只要「夹在忙碌之间」的有限空隙，所以扫描的起点应当是第一段忙碌的结束时刻，而不是 0 或负无穷。

「每名员工的区间已有序」这条信息是个诱饵，也是个信号。诱饵的一面是：它容易让人以为必须做 $k$ 路归并才能利用这份有序性。信号的一面是：如果 $k$ 很大而每人的区间很少，用小顶堆做 $k$ 路归并确实能把排序的 $O(n \log n)$ 降到 $O(n \log k)$。但本题的规模下两者差别不大，而先拉平再统一排序的写法短得多、出错面小得多，是面试中更稳的选择。

边界：可能所有人都没有任何日程，此时忙碌区间集合为空，答案是空列表；可能只有一段忙碌区间，同样没有夹在中间的空隙；不同员工的忙碌区间可以任意重叠、甚至一段完全包含另一段，合并时必须处理包含关系；同一名员工内部的区间保证不重叠，但跨员工没有任何保证。

解法：拉平后排序并合并忙碌段

核心思路

先看一个自然但笨重的思路：把时间轴离散化，或者按员工逐个求空闲区间的交集——先算第一个人的空闲，再与第二个人的空闲求交，依次做下去。逻辑上没错，但每次求交都要处理两组区间的对齐，代码冗长且容易在边界上出错；若时间范围很大，离散化更是自找麻烦。瓶颈在于：我们在「空闲」这个补集上做运算，而补集的表示天生比原集合麻烦（要处理开头和结尾的无限区间）。

换到原集合上：所有员工的空闲交集，等价于所有忙碌区间并集的补集。而求区间并集有一个标准套路——按左端点排序后线性扫描合并。合并过程中产生的「断裂处」，正是我们要的空闲区间。于是根本不需要先算并集再取补，可以在合并的同一趟扫描里顺手把空隙收集出来。

具体做法是：把所有员工的忙碌区间不加区分地倒进一个列表 all，按 start 升序排序，然后维护一个变量 curEnd，含义是「到目前为止扫过的所有区间所覆盖的、从最左端延伸出来的连续忙碌段的右端点」。不变量是：

在处理第 i 个区间之前，curEnd 等于 all[0..i-1] 这些区间的并集中，包含 all[0].start 的那一个连通块的右端点；且时间轴上 $[\,all[0].start,\ curEnd\,]$ 之外、小于 curEnd 的部分已经全部被判定完毕。

由于已按左端点升序排序，新区间的 start 一定不小于之前所有区间的 start，于是只有两种情况：

其一，interval.start > curEnd。说明当前区间与已合并段之间断开了，$(curEnd,\ interval.start)$ 这一段时间里没有任何人忙碌——因为所有左端点小于 interval.start 的区间都已经被扫过、它们的覆盖范围都不超过 curEnd。于是把 [curEnd, interval.start] 记入答案，然后开启新的连通块，curEnd = interval.end。

其二，interval.start <= curEnd。说明当前区间与已合并段有重叠或恰好相接，不产生空隙，只需要把 curEnd 向右扩张：curEnd = max(curEnd, interval.end)。这里的 max 不能省——当前区间可能被之前的某个长区间完全包含（例如已合并到 10，新区间是 [5,6]），此时直接赋值会让 curEnd 倒退，凭空造出一段根本不存在的空闲。

判定用严格的 > 而不是 >=，恰好排除了「首尾相接」的情形：interval.start == curEnd 时空隙长度为 0，不是合法答案。

最后，curEnd 的初值取 all[0].end（排序后第一个区间的右端点），循环从下标 1 开始。这样自然跳过了「第一段忙碌之前的无限空闲」，也不需要任何哨兵值。

解题步骤

把 schedule 中所有员工的区间拉平进一个列表 all。为什么可以不区分员工：我们要的是全体忙碌区间的并集，来源是谁完全不影响并集的形状；保留员工信息反而会诱使人去写多路合并的复杂逻辑。

all 为空时直接返回空列表。为什么必须拦截：后面要访问 all.get(0)，空列表会越界。这是唯一需要的特判。

按 start 升序排序。为什么排左端点而不是右端点：线性合并的正确性依赖「已扫过的区间的左端点都不大于当前区间的左端点」，这样才能断言「curEnd 右侧到 interval.start 之间不可能藏着别的忙碌区间」。按右端点排序会破坏这个断言。

curEnd 初始化为 all.get(0).end，循环从 i = 1 开始。为什么不从 0 开始并把 curEnd 初始化为负无穷：那样第一个区间会被判定为「产生空隙」，凭空输出一段从负无穷开始的空闲；题目只要夹在忙碌之间的有限空隙。

若 interval.start > curEnd，把 [curEnd, interval.start] 加入答案。为什么这段一定是全员空闲：所有左端点小于 interval.start 的区间都已扫过，它们的右端点都不超过 curEnd（这正是不变量保证的），因此这段时间没有任何人忙。为什么用严格大于：等于时空隙长度为 0，不是合法区间。

无论是否产生空隙，都执行 curEnd = max(curEnd, interval.end)。为什么要取最大值：当前区间可能被之前的长区间完全包含，直接赋值会让 curEnd 倒退，导致后续误判出不存在的空隙。为什么在产生空隙的分支里也要更新：那一支开启了新的连通块，interval.end 必然大于旧的 curEnd，max 的结果就是 interval.end，逻辑统一，不必分开写。

返回收集到的区间列表。为什么结果天然有序：区间是按扫描顺序追加的，而扫描顺序按左端点升序，所以产出的空隙也必然升序。

以 具体用例 schedule = [[[1,2],[5,6]], [[1,3]], [[4,10]]] 走一遍，预期答案是 [[3,4]]。

拉平：all = [[1,2], [5,6], [1,3], [4,10]]。
排序（按 start 升序）：all = [[1,2], [1,3], [4,10], [5,6]]。注意 [1,2] 与 [1,3] 左端点相同，谁在前都不影响结果——因为后面统一用 max 扩张 curEnd。

初始化：curEnd = all[0].end = 2。含义是「目前已知从时刻 1 开始的连续忙碌段延伸到 2」。

i = 1，区间 [1,3]：start = 1，1 > 2 不成立，说明它与已合并段重叠。不产生空隙。更新 curEnd = max(2, 3) = 3。此时已知 [1,3] 整段都有人忙。
i = 2，区间 [4,10]：start = 4，4 > 3 成立。断言此刻成立：所有左端点小于 4 的区间（即 [1,2] 与 [1,3]）都已扫过，右端点最大是 3，所以时刻 3 到 4 之间没有任何人忙。记入答案 [3,4]。更新 curEnd = max(3, 10) = 10。
i = 3，区间 [5,6]：start = 5，5 > 10 不成立，不产生空隙。更新 curEnd = max(10, 6) = 10——这里正是 max 的价值所在：[5,6] 被 [4,10] 完全包含，若写成 curEnd = interval.end 会把 curEnd 从 10 退回 6，而后续若还有一个区间 [8,9]，就会被误判成 8 > 6 从而输出一段根本不存在的空闲 [6,8]。

循环结束，返回 [[3,4]]，与预期一致。

再看一个体现「首尾相接不产生空隙」的用例 schedule = [[[1,3]], [[3,5]]]：拉平排序后 all = [[1,3], [3,5]]，curEnd = 3；i = 1 时 start = 3，3 > 3 不成立，不产生空隙，curEnd 更新为 5。返回空列表。正确——时刻 3 前后无缝衔接，没有一丝可用时间。若判定误写成 >=，就会输出一个长度为 0 的 [3,3]。

代码实现

class Solution {
    // 单个员工区间已按时间有序，跨员工合并后再统一排序即可形成一条扫描线。
    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        List<Interval> all = new ArrayList<>();
        for (List<Interval> employee : schedule) {
            all.addAll(employee);
        }

        List<Interval> res = new ArrayList<>();
        if (all.isEmpty()) {
            return res;
        }

        all.sort((a, b) -> Integer.compare(a.start, b.start));

        int curEnd = all.get(0).end;
        for (int i = 1; i < all.size(); i++) {
            Interval interval = all.get(i);
            if (interval.start > curEnd) {
                res.add(new Interval(curEnd, interval.start));
            }
            curEnd = Math.max(curEnd, interval.end);
        }

        return res;
    }
}

func employeeFreeTime(schedule [][]*Interval) []*Interval {
    // 单个员工区间已按时间有序，跨员工合并后再统一排序即可形成一条扫描线。
    all := make([]*Interval, 0)
    for _, employee := range schedule {
        all = append(all, employee...)
    }

    res := make([]*Interval, 0)
    if len(all) == 0 {
        return res
    }

    sort.Slice(all, func(i, j int) bool {
        return all[i].Start < all[j].Start
    })

    curEnd := all[0].End
    for i := 1; i < len(all); i++ {
        interval := all[i]
        if interval.Start > curEnd {
            res = append(res, &Interval{Start: curEnd, End: interval.Start})
        }
        if interval.End > curEnd {
            curEnd = interval.End
        }
    }

    return res
}

复杂度分析

时间复杂度：$O(n \log n)$，其中 $n$ 是全体员工的忙碌区间总数。凭什么：拉平是 $O(n)$，排序是 $O(n \log n)$ 并构成瓶颈，随后的合并扫描每个区间只处理一次、内部只有比较和取最大，是 $O(n)$。如果改用小顶堆做 $k$ 路归并（利用每名员工内部已有序的条件），可以降到 $O(n \log k)$，$k$ 为员工数；在 $k \ll n$ 时更优，但代码复杂度明显上升。

空间复杂度：$O(n)$。凭什么：all 列表持有全部 $n$ 个区间的引用，排序本身在 Java 中对对象数组使用 TimSort 需要 $O(n)$ 辅助空间；答案列表最多含 $n - 1$ 个空隙。没有额外的时间轴数组，因此与时间范围的大小无关——这正是区间扫描相对于「离散化打标记」的优势。

关键点总结

求「所有集合的交集」时，先看它的补集是不是更好求。这里「全员空闲的交集」直接做要逐人求交，而换成「全体忙碌的并集的补」之后，只剩一次排序加一次扫描。补集转换是区间类问题最值钱的一步变形。

区间合并的通用骨架是：按左端点排序 + 一个 curEnd 变量线性扫描。左端点有序是断言「curEnd 之后到当前区间之间必然是空白」的前提，这条断言就是整个线性扫描的正确性来源。56、57、435、1288 等题共用同一副骨架，区别只在扫描时收集什么。

curEnd = max(curEnd, end) 里的 max 是为了处理包含关系，不是可省的保险。忘记它时，一个被完全包含的短区间会让 curEnd 倒退，凭空造出不存在的空隙——这是区间合并里最经典的错误。

端点的开闭要落到比较符号上。本题要求空隙长度严格为正，所以判定用 > 而非 >=；若题目改成「相接也算断开」，符号就要跟着改。写之前先问一句「相等时算重叠还是算断开」。

初值的选择要让主逻辑自然跳过不该产出的部分。curEnd 取第一个区间的右端点、循环从下标 1 开始，等价于声明「第一段忙碌之前的无限空闲不在讨论范围内」，比用负无穷哨兵再事后过滤干净得多。

面试视角：面试官问这题，最想听到的就是那句「全员空闲 = 全体忙碌区间并集的空隙」。说出这句话之后代码几乎是模板。常见追问有两个：一是「每名员工的区间已经有序，你为什么还要全局排序」——答「可以用小顶堆做 $k$ 路归并降到 $O(n \log k)$，但本题规模下排序更简洁，这是可读性与常数的权衡」；二是「如果日程会动态增删呢」——那就该上区间树或者按时间戳做差分事件流（+1 表示有人开始忙、-1 表示结束），扫描时统计当前忙碌人数，人数归零的那段就是空闲。能把差分事件流这条路线也讲出来，说明你理解扫描线的一般形式而不只是背了区间合并模板。

易错点总结

错误写法：curEnd = interval.end（不取最大值） → 用例 schedule = [[[1,10]], [[2,3]], [[8,9]]]，排序后 all = [[1,10],[2,3],[8,9]]；扫到 [2,3] 时 curEnd 从 10 退回 3，扫到 [8,9] 时 8 > 3 成立，输出一段根本不存在的空闲 [3,8]，而正确答案是空列表。

错误写法：判定写成 interval.start >= curEnd → 用例 schedule = [[[1,3]], [[3,5]]]，时刻 3 首尾相接，该写法输出 [3,3] 这个长度为 0 的区间；正确答案是空列表。

错误写法：按 end 排序而不是按 start → 用例 schedule = [[[1,2]], [[3,4]], [[2,10]]]，按 end 排序得 [[1,2],[3,4],[2,10]]；curEnd = 2，扫到 [3,4] 时 3 > 2 成立，输出空闲 [2,3]。但忙碌区间的并集其实是 [1,10] 连成一片，正确答案是空列表。左端点无序时「curEnd 与当前区间之间没有别的忙碌区间」这条断言就不成立了。

错误写法：curEnd 初始化为 0 或 Integer.MIN_VALUE，循环从 i = 0 开始 → 用例 schedule = [[[1,3]]]，第一轮就判定 1 > 0 成立，输出 [0,1] 这段本不该存在的「开工前空闲」；正确答案是空列表。

错误写法：不做拉平，而是按员工逐个与结果求交集 → 逻辑可行但实现冗长，且极易在「一个人完全没有日程」时把结果错误地清空；用例 schedule = [[[1,3]], []]，第二个人全天空闲不应该影响答案，但按交集写法若没特判空日程，会把结果误判成整条时间轴。

错误写法：忘记 all 为空的特判 → 用例 schedule = [[], []]（所有人都没有日程），all.get(0) 直接抛越界异常。

错误写法：只对每名员工内部的区间做合并，然后简单地把各人结果拼起来 → 用例 schedule = [[[1,2],[5,6]], [[1,3]], [[4,10]]]，每人内部本就无重叠，合并毫无作用；真正需要合并的是跨员工的重叠，不拉平就永远发现不了。

错误写法：产出空隙的分支里 continue，跳过 curEnd 的更新 → 用例 schedule = [[[1,2]], [[4,10]], [[5,6]]]，扫到 [4,10] 输出 [2,4] 后没更新 curEnd（仍是 2），扫到 [5,6] 时 5 > 2 成立，又输出一段错误的 [2,5]。无论走哪个分支，curEnd 都必须更新。

错误写法：认为「每名员工的区间已有序」意味着拉平后整体也有序，于是省掉排序 → 用例 schedule = [[[5,6]], [[1,3]]]，拉平后是 [[5,6],[1,3]]，curEnd = 6，扫到 [1,3] 时不产生空隙，返回空列表；正确答案是 [[3,5]]。有序性只在员工内部成立，跨员工必须重新排序或做多路归并。

错误写法：Go 中比较函数写成 all[i].Start <= all[j].Start → sort.Slice 要求传入的是严格弱序（less），用 <= 会让相等元素互相「小于」对方，行为未定义，某些输入下会 panic 或产生错误顺序。

相似题目

题目	难度	考察点
56. 合并区间	中等	同一副扫描骨架，但输出的是合并后的忙碌段本身而不是段与段之间的空隙
57. 插入区间	中等	原区间已有序，只需三段式地处理新区间左侧、重叠、右侧，可做到 $O(n)$ 无需排序
986. 区间列表的交集	中等	求两组有序区间的交集，用双指针同时推进，考的是「谁的右端点小就移谁」
253. 会议室 II	中等	求最大同时重叠数，需要小顶堆维护结束时间或用差分事件流统计峰值
252. 会议室	简单	只判断是否存在任意重叠，排序后相邻两两比较即可，是本题的最简化版
435. 无重叠区间	中等	求最少删除数，必须按右端点排序做贪心，与本题的排序键恰好相反
1288. 删除被覆盖区间	中等	排序键要「左端点升序、右端点降序」，专门用来暴露包含关系
452. 用最少数量的箭引爆气球	中等	求最少的公共穿刺点，同样按右端点贪心，端点相接算作可共用
228. 汇总区间	简单	在已排序的整数序列上找连续段，是「扫描并在断裂处结算」的最基础形态
LCR 074. 合并区间	中等	与 56 同题，可直接套用