2022-06-25：给定一个正数n, 表示有0~n-1号任务，给定一个长度为n的数组time，time[i]表示i号任务做完的时间，给定一个二维数组mat

原创

福大大架构师每日一题

发布于 2022-06-25 12:39:41

4070

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

2022-06-25：给定一个正数n, 表示有0~n-1号任务，

给定一个长度为n的数组time，timei表示i号任务做完的时间，

给定一个二维数组matrix，

matrixj = {a, b} 代表：a任务想要开始，依赖b任务的完成，

只要能并行的任务都可以并行，但是任何任务只有依赖的任务完成，才能开始。

返回一个长度为n的数组ans，表示每个任务完成的时间。

输入可以保证没有循环依赖。

来自美团。3.26笔试。

答案2022-06-25：

拓扑排序基础上做动态规划。

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

fn main() {
    let mut time:Vec<i32>=vec![5,3,4,2,7];
    let mut matrix:Vec<Vec<i32>>=vec![vec![0,1],vec![0,2],vec![1,2],vec![3,1],vec![4,0]];
    let ans = finish_time(5,&mut time,&mut matrix);
    println!("ans = {:?}", ans);
}

fn finish_time(n: i32, time: &mut Vec<i32>, matrix: &mut Vec<Vec<i32>>) -> Vec<i32> {
    let mut nexts: Vec<Vec<i32>> = vec![];
    for i in 0..n {
        nexts.push(vec![]);
    }
    let mut in0: Vec<i32> = vec![];
    for _ in 0..n {
        in0.push(0);
    }
    for line in matrix.iter() {
        nexts[line[1] as usize].push(line[0]);
        in0[line[0] as usize] += 1;
    }
    let mut zero_in_queue: Vec<i32> = vec![];
    let mut ans: Vec<i32> = vec![];
    for _ in 0..n {
        ans.push(0);
    }
    for i in 0..n {
        if in0[i as usize] == 0 {
            zero_in_queue.push(i);
        }
    }
    while zero_in_queue.len() > 0 {
        let cur = zero_in_queue[0];
        zero_in_queue.remove(0);
        ans[cur as usize] += time[cur as usize];
        for next in nexts[cur as usize].iter() {
            ans[*next as usize] = get_max(ans[*next as usize], ans[cur as usize]);
            in0[*next as usize] -= 1;
            if in0[*next as usize] == 0 {
                zero_in_queue.push(*next);
            }
        }
    }
    return ans;
}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}