题目：单核CPU任务调度
知识点队列优先级队列
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
现在有一个CPU和一些任务需要处理，已提前获知每个任务的任务ID、优先级、所需执行时间和到达时间。
CPU同时只能运行一个任务，请编写一个任务调度程序，采用“可抢占优先权调度”调度算法进行任务调度，规则如下：
如果一个任务到来时，CPU是空闲的，则CPU可以运行该任务直到任务执行完毕。但是如果运行中有一个更高优先级的任务到来，则CPU必须暂停当前任务去运行这个优先级更高的任务；
如果一个任务到来时，CPU正在运行一个比它优先级更高的任务时，新到达的任务必须等待；
当CPU空闲时，如果还有任务在等待，CPU会从这些任务中选择一个优先级最高的任务执行，相同优先级的任务选择到达时间最早的任务。
输入描述：
输入有若干行，每一行有四个数字（均小于108），分别为任务ID，任务优先级，执行时间和到达时间。每个任务的任务ID不同，优先级数字越大优先级越高，并且相同优先级的任务不会同时到达。
输入的任务已按照到达时间从小到达排列，并且保证在任何时间，处于等待的任务不超过10000个。
输出描述：
按照任务执行结束的顺序，输出每个任务的任务ID和对应的结束时间。
示例1
输入：
1 3 5 1
2 1 5 10
3 2 7 12
4 3 2 20
5 4 9 21
6 4 2 22
输出：
1 6
3 19
5 30
6 32
4 33
2 35
解题思路：
关键点：使用优先级队列PriorityQueue来放置任务。
1、任务1进来，因为当前队列为空，所以直接加入队列，记录任务开始时间为1
队列中：任务1（1 3 5 1）
2、任务2进来，求出两任务的时间间隙10-1=9，取队列中最上层任务1，所需时间为5，说明时间间隙中可以完成任务，输出第一个任务1 6；更新任务开始时间为10，将任务2放入队列
队列中：任务2（2 1 5 10）
3、任务3进来，求出两任务的时间间隙12-10=2，取队列中最上层任务2，所需时间为5，说明时间间隙中不能完成任务，因为有2个时间的间隙，所有需要更新任务2的所需时间5-2=3；更新任务开始时间为12，将任务3放入队列
队列中：任务3（3 2 7 12）、任务2（2 1 3 10）（任务3的优先级高于任务2）
4、任务4进来，求出两任务的时间间隙20-12=8，取队列中最上层任务3，所需时间为7，说明时间间隙中能完成任务3，输出3 19；而20-19=1，时间剩余1，再取队列最上层任务2，而任务2需要3个时间，所有不能完成，更新所需时间3-1=2；更新任务开始时间为20，将任务2和任务4放入队列
队列中：任务4（4 3 2 20）、任务2（2 1 2 10）（任务4的优先级高于任务2）
5、任务5进来，求出两任务的时间间隙21-20=1，取队列中最上层任务4，所需时间为2，所有不能完成，更新所需时间2-1=1；更新任务开始时间为21；将任务5和任务4放入队列
队列中：任务5（5 4 9 21）、任务4（4 3 1 20）、任务2（2 1 2 10）
6、任务6进来，求出两任务的时间间隙22-21=1，取队列中最上层任务5，所需时间为9，所有不能完成，更新所需时间9-1=8；更新任务开始时间为22；将任务6和任务5放入队列
队列中：任务5（5 4 8 21）、任务6（6 4 2 22）、任务4（4 3 1 20）、任务2（2 1 2 10）
7、遍历队列中的任务：
1）任务5：22+8=30、输出5 30
2）任务6：30+2=32、输出6 32
3）任务4：32+1=33、输出4 33
4）任务2：33+2=35、输出2 35
这个算法只有100分，错误的用例也是非常长，显示不全，有可能是需要使用BigDecimal，大家看看有什么其他问题！
全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。
真题库：https://www.yuque.com/codernav.com/od
代码实现：
package com.codernav.demo.hwod.exam;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
/**
* @title 单核CPU任务调度
* @Description 现在有一个CPU和一些任务需要处理，已提前获知每个任务的任务ID、优先级、所需执行时间和到达时间。
* CPU同时只能运行一个任务，请编写一个任务调度程序，采用“可抢占优先权调度”调度算法进行任务调度，规则如下：
* 如果一个任务到来时，CPU是空闲的，则CPU可以运行该任务直到任务执行完毕。但是如果运行中有一个更高优先级的任务到来，则CPU必须暂停当前任务去运行这个优先级更高的任务；
* 如果一个任务到来时，CPU正在运行一个比它优先级更高的任务时，新到达的任务必须等待；
* 当CPU空闲时，如果还有任务在等待，CPU会从这些任务中选择一个优先级最高的任务执行，相同优先级的任务选择到达时间最早的任务。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/28
*/
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
List<Task> tasks = new ArrayList<>();
while (input.hasNextInt()) {
//因为原题没有输出条件，所以这边使用for循环来完成输出
//for(int i=0; i<8; i++){
int id = input.nextInt();
int p = input.nextInt();
int need = input.nextInt();
int start = input.nextInt();
tasks.add(new Task(id, p, need, start));
}
//优先级队列
PriorityQueue<Task> queue = new PriorityQueue<>();
long time = 0;
for (Task t : tasks) {
//两任务开始的相隔时间
long h = t.start - time;
while (!queue.isEmpty() && h > 0) {
if (h >= queue.peek().need) {
//中间的空余时间满足上一个任务执行
Task tmp = queue.poll();
//执行完上个任务所剩下的时间
h -= tmp.need;
//上个任务执行完的时间
time += tmp.need;
//输出执行完的任务
System.out.println(tmp.id + " " + time);
} else {
Task tmp = queue.peek();
//更新任务的所需要时间（减去两任务之间的空余时间）
tmp.need -= h;
//更新时间
time += h;
//没有任务能完成直接退出
break;
}
}
//更新时间
if (time < t.start) time = t.start;
//加入优先级队列
queue.add(t);
}
//根据优先级输出任务
while (!queue.isEmpty()) {
Task t = queue.poll();
time += t.need;
System.out.println(t.id + " " + time);
}
}
public static class Task implements Comparable<Task> {
int id;
int p;
int need;
int start;
public Task(int id, int p, int need, int start) {
this.id = id;
this.p = p;
this.need = need;
this.start = start;
}
@Override
public int compareTo(Task o) {
if (this.p == o.p) {
return this.start - o.start;
}
return o.p - this.p;
}
}
}
相关文章
