2022-10-07：给定员工的 schedule 列表，表示每个员工的工作时间。每个员工都有一个非重叠的时间段 Interv

福大大架构师每日一题

发布于 2022-11-06 02:24:08

35200

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2022-10-07：给定员工的 schedule 列表，表示每个员工的工作时间。

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

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

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

输出：[[5,6],[7,9]]。

答案2022-10-07：

哈希表+排序。扫描线算法。

代码用rust编写。代码如下：

use std::collections::HashSet;
fn main() {
    let mut schedule = vec![
        vec![Interval::new(1, 3), Interval::new(6, 7)],
        vec![Interval::new(2, 4)],
        vec![Interval::new(2, 5), Interval::new(9, 12)],
    ];
    let ans = employee_free_time(&mut schedule);
    println!("ans = {:?}", ans);
}
#[derive(Debug)]
struct Interval {
    start: i32,
    end: i32,
}
impl Interval {
    fn new(s: i32, e: i32) -> Self {
        Self { start: s, end: e }
    }
}

// 哈希表！
fn employee_free_time(schedule: &mut Vec<Vec<Interval>>) -> Vec<Interval> {
    let mut arr: Vec<Vec<i32>> = vec![];
    for people in schedule.iter() {
        for interval in people.iter() {
            // 0 开始时间点，有个员工要上线
            // 1 结束时间点，有个员工要下线
            arr.push(vec![interval.start, interval.end, 0]);
            arr.push(vec![interval.end, interval.end, 1]);
        }
    }
    arr.sort_by(|a, b| a[0].cmp(&b[0]));
    let mut set: HashSet<i32> = HashSet::new();
    set.insert(arr[0][1]);
    let mut ans: Vec<Interval> = vec![];
    for i in 1..arr.len() as i32 {
        //int[] cur = arr.get(i);
        if arr[i as usize][2] == 0 {
            // 开始时间点来到的时候，来看看有没有空闲时间段
            //  3  7
            if set.len() == 0 && arr[(i - 1) as usize][0] != arr[i as usize][0] {
                ans.push(Interval::new(arr[(i - 1) as usize][0], arr[i as usize][0]));
            }
            // 哈希表填人了，cur[1]
            set.insert(arr[i as usize][1]);
        } else {
            set.remove(&arr[i as usize][0]);
        }
    }
    return ans;
}