2022-05-30把定n*2的二维数组,表示有n个任务。 信息是任务能够开始做的时间,另信息是任务的结束期限,后者一定大于前者,且数值上都是正数, 你作为单线程的人,不能并行处理任务,
2022-05-30:给定一个n*2的二维数组,表示有n个任务。
一个信息是任务能够开始做的时间,另一个信息是任务的结束期限,后者一定大于前者,且数值上都是正数,
你作为单线程的人,不能并行处理任务,但是每个任务都只需要一个单位时间完成,
你需要将所有任务的执行时间,位于开始做的时间和最后期限之间。
返回你能否做到这一点。
来自华为。
答案2022-05-30:
小根堆。先做最紧迫的任务。
代码用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;
}
执行结果如下:
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhhifebf
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
微信运动停用后别人还能看到步数吗
PHP中文网 07-22