2022-06-25: given a positive number n, it means that there are tasks 0~n-1. Given an array of length N, time[i] means the time when task I is completed. Given a two-dimensional array matrix, matrix[j]

2022-06-25： Give a positive number n, Express 0~n-1 Task ,
Given a length of n Array of time,time[i] Express i When task No ,
Given a two-dimensional array matrix,
matrix[j] = {a, b} representative ：a Task wants to start , rely on b The completion of the task ,
Any task that can be parallelized can be parallelized , But any task can only be completed by tasks that depend on it , To start .
Returns a length of n Array of ans, Indicates the completion time of each task .
Input guarantees no circular dependencies .
From meituan .3.26 written examination .

answer 2022-06-25：

Do dynamic planning based on topological sorting .

The code to use rust To write . The code is as follows ：

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
    }
}

The results are as follows ：

---

Zuo Shen java Code