侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【哈希表, 优先队列】员工空闲时间

GabrielxD
2022-06-03 / 0 评论 / 0 点赞 / 29 阅读 / 650 字 / 正在检测是否收录...

题目

759. 员工空闲时间


给定员工的 schedule 列表,表示每个员工的工作时间。

每个员工都有一个非重叠的时间段 Intervals 列表,这些时间段已经排好序。

返回表示 所有 员工的 共同,正数长度的空闲时间 的有限时间段的列表,同样需要排好序。

示例 1:

输入:schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
输出:[[3,4]]
解释:
共有 3 个员工,并且所有共同的
空间时间段是 [-inf, 1], [3, 4], [10, inf]。
我们去除所有包含 inf 的时间段,因为它们不是有限的时间段。

示例 2:

输入:schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
输出:[[5,6],[7,9]]

(尽管我们用 [x, y] 的形式表示 Intervals ,内部的对象是 Intervals 而不是列表或数组。例如,schedule[0][0].start = 1, schedule[0][0].end = 2,并且 schedule[0][0][0] 是未定义的)

而且,答案中不包含 [5, 5] ,因为长度为 0。

注:

  • scheduleschedule[i] 为长度范围在 [1, 50]的列表。
  • 0 <= schedule[i].start < schedule[i].end <= 10^8

注:输入类型于 2019 年 4 月 15 日 改变。请重置为默认代码的定义以获取新方法。

解题

方法一:排序 哈希表

思路

一种简单粗暴的做法:把所有员工的工作区间先扁平化并按照区间左端点进行排序,然后用[【排序, 双指针, 暴力遍历】合并区间](【排序, 双指针, 暴力遍历】合并区间.md)的方法把能合并的区间合并,最后求这些区间对于 (,+)(-\infin, +\infin) 的补集即是所有员工的共同空闲区间(不包括 (,最左端点)(-\infin, 最左端点)(最右端点,+)(最右端点, +\infin))。

代码

class Solution {
    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        List<Interval> list = new ArrayList<>() {{
            schedule.forEach(each -> this.addAll(each));
        }};
        list.sort((a, b) -> a.start - b.start);
        int n = list.size();
        List<Interval> merged = new ArrayList<>();
        for (int left = 0; left < n;) {
            int end = list.get(left).end;
            int right = left + 1;
            while (right < n && list.get(right).start <= end) {
                end = Math.max(list.get(right++).end, end);
            }
            merged.add(new Interval(list.get(left).start, end));
            left = right;
        }
        List<Interval> ans = new ArrayList<>();
        for (int i = 0; i < merged.size() - 1; i++) {
            ans.add(new Interval(merged.get(i).end, merged.get(i + 1).start));
        }
        return ans;
    }
}
0

评论区