Share a processor fairly among several tasks.
What to build
A queue that simulates how an operating system takes turns.
Requirements
- Each task runs for up to
qunits of time, then goes to the back of the queue if it has not finished. - Print each task when it finishes, as
NAME T, where T is the total time passed so far.
Input
The first line has n and q. Each of the next n lines has a name and a time.
Output
One line per task, in the order they finish.
Constraints
n is from 1 to 100. q and each time are from 1 to 1000.
Example
Input:
2 2
a 3
b 1
Output:
b 3
a 4
Why it works
A queue gives each task its turn in order. Putting a task back at the end is what makes the sharing fair.
Examples
Example 1 · Input
2 2 a 3 b 1
Expected output
b 3 a 4
Example 2 · Input
1 5 x 3
Expected output
x 3
Hints
Hint 1
Store each task's name and time left, as a pair, in a queue.
Hint 2
Take the front task, and run it for up to q units.
Hint 3
If it has time left, put it at the back.
Solution
Show one correct solution (try it yourself first)
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
queue<pair<string, int>> tasks;
for (int i = 0; i < n; i++) {
string name;
int t;
cin >> name >> t;
tasks.push(make_pair(name, t));
}
int clock = 0;
while (!tasks.empty()) {
pair<string, int> task = tasks.front();
tasks.pop();
int used = task.second < q ? task.second : q;
clock += used;
task.second -= used;
if (task.second > 0) {
tasks.push(task);
} else {
cout << task.first << " " << clock << endl;
}
}
return 0;
}