Priority Task Scheduler
Problem
A scheduler keeps tasks with a priority (a bigger number is more important). Commands: add name priority puts a task in the scheduler, and run prints the name of the most important task and removes it. If two tasks have the same priority, the one that was added first runs first. If there is no task, run prints idle.
Constraints
- 1 <= commands <= 10^5
- |priority| <= 10^9
Examples
Input
add a 1 add b 3 add c 3 run run run run
Output
b c a idle
Solutions
A priority queue always gives out the best element first, in O(log n). A plain priority comparison is not stable, so a running number is added to break ties first-in, first-out.
/*
* Problem : Process lines.
* Input : Several lines.
* Output : One name per run command.
* Approach: Priority queue.
* Time : O(n log n)
* Space : O(n)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// Step 1: Each task keeps its priority and a running number. The number breaks ties: smaller number = added earlier.
static class Task {
final String name;
final long priority;
final long order;
Task(String name, long priority, long order) {
this.name = name;
this.priority = priority;
this.order = order;
}
}
// This method solves the task. It receives the input and returns the answer.
static String[] solve(String[] lines) {
// Step 2: The queue gives out the task with the biggest priority first. Equal priorities go by order.
java.util.PriorityQueue<Task> queue = new java.util.PriorityQueue<>((first, second) -> {
if (first.priority != second.priority) {
return Long.compare(second.priority, first.priority);
}
return Long.compare(first.order, second.order);
});
long counter = 0;
java.util.List<String> output = new java.util.ArrayList<>();
for (String line : lines) {
String[] part = line.split(" ");
// Step 3: run prints the head of the queue, or idle when the queue is empty.
if (part[0].equals("add")) {
queue.add(new Task(part[1], Long.parseLong(part[2]), counter++));
} else {
Task next = queue.poll();
output.add(next == null ? "idle" : next.name);
}
}
return output.toArray(new String[0]);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
java.util.List<String> all = new java.util.ArrayList<>();
while (scanner.hasNextLine()) {
String line = scanner.nextLine().trim();
if (!line.isEmpty()) {
all.add(line);
}
}
String[] lines = all.toArray(new String[0]);
System.out.println(String.join("\n", solve(lines)));
}
}
Hints (1)
- Why do we need the running number?