Java: A task scheduler with a priority queue

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 print t=T NAME where 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 T with 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);
        }
    }
}

Lesson: Sets, queues and stacks →