写点什么

2022-10-07:给定员工的 schedule 列表,表示每个员工的工作时间。 每个员工都有一个非重叠的时间段 Intervals 列表,这些时间段已经排好序。 返回表示 所有 员工的 共同,正

  • 2022 年 10 月 07 日
    北京
  • 本文字数:996 字

    阅读完需:约 3 分钟

2022-10-07:给定员工的 schedule 列表,表示每个员工的工作时间。 每个员工都有一个非重叠的时间段 Intervals 列表,这些时间段已经排好序。 返回表示 所有 员工的 共同,正

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;}
复制代码


执行结果如下:





左神java代码

发布于: 刚刚阅读数: 3
用户头像

还未添加个人签名 2021.02.15 加入

还未添加个人简介

评论

发布
暂无评论
2022-10-07:给定员工的 schedule 列表,表示每个员工的工作时间。 每个员工都有一个非重叠的时间段 Intervals 列表,这些时间段已经排好序。 返回表示 所有 员工的 共同,正_算法_福大大架构师每日一题_InfoQ写作社区