2022-05-30：给定一个n*2的二维数组，表示有n个任务。
一个信息是任务能够开始做的时间，另一个信息是任务的结束期限，后者一定大于前者，且数值上都是正数，
你作为单线程的人，不能并行处理任务，但是每个任务都只需要一个单位时间完成，
你需要将所有任务的执行时间，位于开始做的时间和最后期限之间。
返回你能否做到这一点。
来自华为。
答案2022-05-30：
小根堆。先做最紧迫的任务。
代码用rust编写。代码如下：
代码语言：rust复制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代码
