Run tasks in order of urgency, choosing a structure that stays fast as tasks keep arriving.
What to build
A priority queue of tasks, built on a binary heap.
Requirements
add P NAMEadds a task with priorityP. A larger number is more urgent.runremoves the most urgent task and prints its name, or printsidlewhen there is none.- Of two tasks with the same priority, the one that was added first runs first.
Input
The first line has q. Each of the next q lines has one command. A name has 1 to 15 lowercase letters.
Output
One line for each run.
Constraints
1 ≤ q ≤ 200, and each priority is from 1 to 100.
Example
Input:
6
add 2 email
add 5 backup
add 5 update
run
run
run
Output:
backup
update
email
Why it works
The work is "add" and "remove the most urgent", again and again. A heap does both in O(log n). A sorted array would be slow to add to, and an unsorted one slow to search.
Examples
6 add 2 email add 5 backup add 5 update run run run
backup update email
2 run add 1 x
idle
Hints
Hint 1
Give each task a number in the order it was added, and keep its priority and name in arrays.
Hint 2
Store task numbers in a heap. Task a goes before task b if its priority is higher, or the priorities are equal and a was added first.
Hint 3
Use that one rule in both sift-up and sift-down.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <string.h>
char names[200][16];
int prio[200];
int heap[200]; /* task numbers, with the most urgent at heap[0] */
int size = 0;
int before(int a, int b) { /* should task a run before task b? */
if (prio[a] != prio[b]) return prio[a] > prio[b];
return a < b;
}
void swap(int i, int j) {
int t = heap[i];
heap[i] = heap[j];
heap[j] = t;
}
void push(int task) {
int i = size++;
heap[i] = task;
while (i > 0 && before(heap[i], heap[(i - 1) / 2])) {
swap(i, (i - 1) / 2);
i = (i - 1) / 2;
}
}
int pop(void) {
int top = heap[0];
heap[0] = heap[--size];
int i = 0;
while (1) {
int l = 2 * i + 1, r = 2 * i + 2, best = i;
if (l < size && before(heap[l], heap[best])) best = l;
if (r < size && before(heap[r], heap[best])) best = r;
if (best == i) break;
swap(i, best);
i = best;
}
return top;
}
int main(void) {
int q, count = 0;
scanf("%d", &q);
for (int i = 0; i < q; i++) {
char cmd[10];
scanf("%9s", cmd);
if (strcmp(cmd, "add") == 0) {
scanf("%d %15s", &prio[count], names[count]);
push(count);
count++;
} else {
if (size == 0) {
printf("idle\n");
} else {
int task = pop();
printf("%s\n", names[task]);
}
}
}
return 0;
}