Schedule work by priority, the way an operating system or a job queue does.
What to build
A scheduler that runs tasks in time slices by priority.
Requirements
- Input: tasks
NAME PRIORITY TIME. Each step, take the task with the highest priority (earlier input first on a tie), run it for one slice of at most 2 time units, and printt=T NAMEwhere T is the time when the slice starts (from 0). - A task with time left goes back into the queue with a new arrival number (behind tasks of equal priority already waiting). When it finishes print
done NAME at Twith the finishing time.
Input
Line 1: n. Then n tasks.
Output
The slices and completions, in order.
Constraints
1 ≤ n ≤ 20; 1 ≤ PRIORITY ≤ 9; 1 ≤ TIME ≤ 10.
Example
Input:
3
backup 1 2
email 5 3
report 5 1
Output:
t=0 email
t=2 report
done report at 3
t=3 email
done email at 4
t=4 backup
done backup at 6
Why it works
The priority queue always hands out the most urgent task, and giving a returning task a new arrival number makes equal priorities take turns.
Examples
Example 1 · Input
3 backup 1 2 email 5 3 report 5 1
Expected output
t=0 email t=2 report done report at 3 t=3 email done email at 4 t=4 backup done backup at 6
Example 2 · Input
1 solo 3 5
Expected output
t=0 solo t=2 solo t=4 solo done solo at 5
Hints
Hint 1
Store tasks as records with a name, a priority and an arrival number; the comparator uses priority (higher first), then arrival.
Hint 2
Keep running tasks out of the queue and put them back with their remaining time.
Solution
Show one correct solution (try it yourself first)
import java.util.*;
public class Main {
record Task(String name, int priority, int left, int arrival) {}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = Integer.parseInt(in.nextLine().trim());
PriorityQueue<Task> queue = new PriorityQueue<>((a, b) -> a.priority() != b.priority() ? b.priority() - a.priority() : a.arrival() - b.arrival());
int arrivals = 0;
for (int i = 0; i < n; i++) {
String[] p = in.nextLine().split(" ");
queue.add(new Task(p[0], Integer.parseInt(p[1]), Integer.parseInt(p[2]), arrivals++));
}
int t = 0;
while (!queue.isEmpty()) {
Task task = queue.poll();
int slice = Math.min(2, task.left());
System.out.println("t=" + t + " " + task.name());
t += slice;
if (task.left() > slice) queue.add(new Task(task.name(), task.priority(), task.left() - slice, arrivals++));
else System.out.println("done " + task.name() + " at " + t);
}
}
}