Skip to content

Instantly share code, notes, and snippets.

@yamadayuki
Last active December 13, 2016 04:24
Show Gist options
  • Save yamadayuki/962fa61547d2f08120b8bed18d002f8d to your computer and use it in GitHub Desktop.
Save yamadayuki/962fa61547d2f08120b8bed18d002f8d to your computer and use it in GitHub Desktop.
The round-robin scheduling.
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_B
// Test Case
// Input
// 5 100
// p1 150
// p2 80
// p3 200
// p4 350
// p5 20
// Output
// p2 180
// p5 400
// p1 450
// p3 550
// p4 800
var MAX = 100000;
var n = 0;
var q = 0;
var now = 0;
var queue = new Queue();
var input = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n')
.map(function (value, index) {
value = value.split(' ');
if (index === 0) {
n = parseInt(value[0]);
q = parseInt(value[1]);
return;
} else {
return new Process(value[0], value[1]);
}
})
.filter(function (value) {
return typeof value !== 'undefined';
})
.forEach(function (value) {
queue.enqueue(value);
});
// Define
function Process(name, time) {
this.name = name;
this.time = parseInt(time);
return this;
}
function Queue() {
this.queue = [];
this.headIndex = 0;
this.tailIndex = 0;
this.n = 0
this.enqueue = function enqueue(p) {
this.queue[this.tailIndex] = p;
this.tailIndex = (this.tailIndex + 1) % MAX;
};
this.dequeue = function dequeue() {
var p = this.queue[this.headIndex];
this.headIndex = (this.headIndex + 1) % MAX;
return p;
}
return this;
};
// Main
while (queue.headIndex !== queue.tailIndex) {
var currentProcess = queue.dequeue();
var c = Math.min(q, currentProcess.time);
currentProcess.time -= c;
now += c;
if (currentProcess.time > 0) {
queue.enqueue(currentProcess);
} else {
console.log(currentProcess.name + ' ' + now.toString());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment