leetcode
leetcode 651 ~ 700
员工空闲时间

员工空闲时间

难度:

标签:

题目描述

代码结果

运行时间: 55 ms, 内存: 17.5 MB

/*
题目思路:
1. 将所有员工的工作时间段合并到一个流中。
2. 按照时间段的起始时间对合并后的流进行排序。
3. 使用reduce操作遍历排序后的时间段流，寻找两个相邻时间段之间的空闲时间。
*/

import java.util.*;
import java.util.stream.*;

class Interval {
    public int start;
    public int end;
    public Interval() {}
    public Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

public class EmployeeFreeTime {
    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        List<Interval> allIntervals = schedule.stream()
            .flatMap(Collection::stream)
            .sorted(Comparator.comparingInt(a -> a.start))
            .collect(Collectors.toList());

        List<Interval> freeTime = new ArrayList<>();
        allIntervals.stream().reduce((a, b) -> {
            if (a.end < b.start) {
                freeTime.add(new Interval(a.end, b.start));
            }
            return new Interval(a.start, Math.max(a.end, b.end));
        });
        return freeTime;
    }
}

解释

方法:

这个题解的思路首先是将所有员工的时间间隔收集到一个列表中，然后根据每个时间间隔的开始时间将这个列表排序。排序后，它遍历排序好的时间间隔列表，比较当前时间间隔的开始时间与前一个时间间隔的结束时间，以确定两者之间是否存在空闲时间。如果存在空闲时间（即当前时间间隔的开始时间大于前一个时间间隔的结束时间），则创建一个新的时间间隔来表示这段空闲时间，并将其添加到结果列表中。遍历结束后，返回包含所有空闲时间的列表。

时间复杂度:

O(n log n)

空间复杂度:

O(n)

代码细节讲解

相关问题

合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

 

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

 

提示：

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104

区间列表的交集

给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。

返回这 两个区间列表的交集 。

形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。

两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。

 

示例 1：

输入：firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

示例 2：

输入：firstList = [[1,3],[5,9]], secondList = []
输出：[]

示例 3：

输入：firstList = [], secondList = [[4,8],[10,12]]
输出：[]

示例 4：

输入：firstList = [[1,7]], secondList = [[3,10]]
输出：[[3,7]]

 

提示：

  • 0 <= firstList.length, secondList.length <= 1000
  • firstList.length + secondList.length >= 1
  • 0 <= starti < endi <= 109
  • endi < starti+1
  • 0 <= startj < endj <= 109
  • endj < startj+1
字符串中的加粗单词找出变位映射