2022-06-25：给定一个正数n, 表示有0~n-1号任务，
给定一个长度为n的数组time，time[i]表示i号任务做完的时间，
给定一个二维数组matrix，
matrix[j] = {a, b} 代表：a任务想要开始，依赖b任务的完成，
只要能并行的任务都可以并行，但是任何任务只有依赖的任务完成，才能开始。
返回一个长度为n的数组ans，表示每个任务完成的时间。
输入可以保证没有循环依赖。
来自美团。3.26笔试。
答案2022-06-25：
拓扑排序基础上做动态规划。
代码用rust编写。代码如下：
代码语言：javascript复制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
}
}
执行结果如下：
***
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_04_2_week/Code04_AllJobFinishTime.java)
