LeetCode 759. 员工空闲时间

2022-04-06 HGNULB 约 4 分钟

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

分类

LeetCode CodeTop 困难未解决会员题 2-5 阿里微软滴滴

题目描述

✅ 759. 员工空闲时间

题意分析

日程记录的是员工忙碌的时间，要求找出所有员工都空闲的有限正长度区间，并按时间顺序返回。只要有一个员工忙碌，该时段就不能算共同空闲，因此应先求所有忙碌区间的并集，再找并集相邻部分之间的空隙。

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

核心思路

[!blue]

将所有员工的忙碌区间放入同一列表，按起点从小到大排序。扫描时，用 curEnd 保存已经处理的忙碌区间能到达的最右端点，也就是当前最后一段忙碌并集的结束位置。

若下一区间的起点 start > curEnd，已处理的区间都不会晚于 curEnd 结束，未处理的区间又都不会早于 start 开始，所以中间的 [curEnd, start] 没有任何人忙碌，正是一个共同空闲区间。

若 start <= curEnd，新区间与最后一段忙碌时间重叠或相接，不产生正长度空隙。两种情况都更新 curEnd = max(curEnd, end)：新区间可能延长覆盖，也可能完全被已有区间包含，不能让覆盖边界向左退。

每个有限空闲区间都位于相邻的忙碌并集之间，扫描到后一个忙碌区间时就会被发现，因此不会遗漏。第一段之前和最后一段之后的空闲向无穷延伸，不属于题目要求的有限区间。

解题步骤

收集所有忙碌区间到新列表；若没有区间，返回空结果。

按起点排序，用第一段的结束时间初始化 curEnd。

从第二段开始扫描，若起点严格大于 curEnd，添加空闲区间 [curEnd, start]。

用当前结束时间更新最右覆盖端点，继续处理下一段。

嵌套区间不会缩短已有覆盖；首尾相接时只共享一个端点，没有正长度空闲。扫描过程中按时间发现空隙，结果自然已经有序，无需再排序。

代码实现

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;
    }
}

import "sort"

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+1))$，N 为全部忙碌区间数量。

空间复杂度：$O(N)$，拉平引用列表与排序辅助。

关键点总结

[!green]

curEnd 跟踪最新覆盖边界，跨过空隙后已属于新的忙碌连通段。

首尾相接没有正长度空隙。

排序的是新建的引用列表，不改变员工原日程顺序，也不修改区间端点。

易错点总结

[!yellow]

直接用当前结束时间覆盖，会在嵌套区间后造出假空隙。

条件用大于等于，会输出零长度区间。

只按每个人内部顺序拼接，不能保证全局有序。

相似题目

题目	难度	关联与区别
56. 合并区间	中等	先合并所有忙碌区间，再取相邻合并区间之间的有限空隙。
23. 合并 K 个升序链表	困难	各员工日程内部有序，可通过多路归并按起点依次处理，不必重新排序所有区间。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2022/85991345

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！