题目描述
链接:https://ac.nowcoder.com/acm/problem/20030
来源:牛客网
写一个程序来模拟操作系统的进程调度。假设该系统只有一个CPU,每一个进程的到达时间,执行时间和运行优先级都是已知的。其中运行优先级用自然数表示,数字越大,则优先级越高。
如果一个进程到达的时候CPU是空闲的,则它会一直占用CPU直到该进程结束。除非在这个过程中,有一个比它优先级高的进程要运行。在这种情况下,这个新的(优先级更高的)进程会占用CPU,而老的只有等待。
如果一个进程到达时,CPU正在处理一个比它优先级高或优先级相同的进程,则这个(新到达的)进程必须等待。一旦CPU空闲,如果此时有进程在等待,则选择优先级最高的先运行。如果有多个优先级最高的进程,则选择到达时间最早的。
输入
1 1 5 3
2 10 5 1
3 12 7 2
4 20 2 3
5 21 9 4
6 22 2 4
7 23 5 2
8 24 2 4
输出
1 6
3 19
5 30
6 32
8 34
4 35
7 40
2 42
思路
用优先队列大家都能想到,按照题目给的条件进行模拟,先按照优先级从大到小进行排序,如果优先级相同,则按照到达时间短的排前面。本题是一个抢占式的进程调度,如果当前时间有进程占用CPU,而到达的进程优先级比它高,那么就会抢占。因此我们可以按照这个思路进行模拟。
如果当前进程执行时间 < 下一个进程到达时间 - 当前时间。那么就可能会被抢占,先放到队列里。
否则,该进程会执行完。
这里进程是按照时间顺序进入的优先队列。
注意:这里要用PrintWriter,不能使用System.out.println(),由于可以手动控制缓冲区的刷新,PrintWriter 在处理大量数据时可能比 System.out.println() 更高效。
代码
import java.io.PrintWriter;
import java.util.*;public class Main{public static void main(String[] args) {Scanner in = new Scanner(System.in);PrintWriter out = new PrintWriter(System.out);PriorityQueue<Process> pq = new PriorityQueue<>();List<int[]> ans = new ArrayList<>();List<Process> list = new ArrayList<>();while(in.hasNext()) {int id = in.nextInt();int arrTime = in.nextInt();int execTime = in.nextInt();int prior = in.nextInt();list.add(new Process(id, arrTime, execTime, prior));}int curTime = 0;int ind = 0;while (ind < list.size()) {if (pq.isEmpty()) {curTime = list.get(ind).arrivalTime; // 当前时间是下一个进程到达的时间} else {Process top = pq.poll();int diff = Math.min(top.executionTime, list.get(ind).arrivalTime - curTime);curTime += diff;top.executionTime -= diff;if (top.executionTime == 0) {ans.add(new int[] {top.id, curTime});} else {pq.offer(top);}}while (ind < list.size() && list.get(ind).arrivalTime <= curTime) {pq.offer(list.get(ind++));}}while (!pq.isEmpty()) {Process a = pq.poll();curTime += a.executionTime;ans.add(new int[]{a.id, curTime});}for (int[] a : ans) {out.println(a[0] + " " + a[1]);}out.close();}
}
class Process implements Comparable {int id;int arrivalTime;int executionTime;int priority;public Process(int id, int arrivalTime, int executionTime, int priority) {this.id = id;this.arrivalTime = arrivalTime;this.executionTime = executionTime;this.priority = priority;}@Overridepublic int compareTo(Object o) {if (this.priority != ((Process) o).priority) {return Integer.compare(((Process) o).priority, this.priority); // 从大到小排序} else {return Integer.compare(this.arrivalTime, ((Process) o).arrivalTime); // 从小到大排序}}
}