前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2022-05-30:给定一个n*2的二维数组,表示有n个任务。一个信息是任务能够开始做的时间,另一个信息是任务的结束期限

2022-05-30:给定一个n*2的二维数组,表示有n个任务。一个信息是任务能够开始做的时间,另一个信息是任务的结束期限

作者头像
福大大架构师每日一题
发布2022-06-04 11:10:23
2880
发布2022-06-04 11:10:23
举报

2022-05-30:给定一个n*2的二维数组,表示有n个任务。

一个信息是任务能够开始做的时间,另一个信息是任务的结束期限,后者一定大于前者,且数值上都是正数,

你作为单线程的人,不能并行处理任务,但是每个任务都只需要一个单位时间完成,

你需要将所有任务的执行时间,位于开始做的时间和最后期限之间。

返回你能否做到这一点。

来自华为。

答案2022-05-30:

小根堆。先做最紧迫的任务。

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

代码语言:javascript
复制
fn main() {
    let mut arr: Vec<Vec<i32>> = vec![vec![1, 4], vec![1, 4], vec![1, 4], vec![1, 4]];
    let ans = can_do(&mut arr);
    println!("ans = {}", ans);
}

// 1 开 7
// 5 闭 end没有用!
pub struct TimePoint {
    // 时间
    time: i32,
    end: i32,
    // add = true time 任务的添加时间
    // add = false time 任务的结束时间
    add: bool,
}

impl TimePoint {
    pub fn new(t: i32, e: i32, a: bool) -> Self {
        Self {
            time: t,
            end: e,
            add: a,
        }
    }
}

fn can_do(jobs: &mut Vec<Vec<i32>>) -> bool {
    if jobs.len() < 2 {
        return true;
    }
    let n = jobs.len() as i32;
    let mut arr: Vec<TimePoint> = vec![];
    for _i in 0..n << 1 {
        arr.push(TimePoint::new(0, 0, false));
    }
    for i in 0..n {
        arr[i as usize] = TimePoint::new(jobs[i as usize][0], jobs[i as usize][1], true);
        arr[(i + n) as usize] = TimePoint::new(jobs[i as usize][1], jobs[i as usize][1], false);
    }
    arr.sort_by(|a, b| a.time.cmp(&b.time));
    let mut heap: Vec<i32> = vec![];
    // 经过一个一个的时间点,遭遇事件:添加时间、检查时间
    let mut i: i32 = 0;
    let mut last_time = arr[0].time;
    while i < arr.len() as i32 {
        if arr[i as usize].add {
            heap.push(arr[i as usize].end);
        } else {
            // 检查时间
            let cur_time = arr[i as usize].time;
            for _j in last_time..cur_time {
                if heap.len() == 0 {
                    break;
                }
                heap.sort_by(|a, b| b.cmp(&a));
                heap.pop();
            }
            heap.sort_by(|a, b| b.cmp(&a));
            if heap.len() > 0 && heap[heap.len() - 1] <= cur_time {
                return false;
            }
            last_time = cur_time;
        }
        i += 1;
    }
    return true;
}

执行结果如下:

***

[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_03_4_week/Code01_ArrangeJob.java)

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-05-30,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档