Skip to content

Instantly share code, notes, and snippets.

@aybabtme
Last active December 29, 2015 12:38
Show Gist options
  • Save aybabtme/7671369 to your computer and use it in GitHub Desktop.
Save aybabtme/7671369 to your computer and use it in GitHub Desktop.
var schedule = function(taskArr) {
// 1st step: sort data by gain (from max to min)
var sortedByGain = insertionSort(taskList, "gain");
var n = sortedByGain.length;
var timeSlot = new Array();
// 2nd step: number the jobs 1,2,3,..,n, then
for (var i = 0; i < n; i++) {
var task = sortedByGain.pop()
// for each job `i`, suppose it has deadline `k`
var k = task.deadline - 1; // 0-indexed
// start at time slot `k`, scan backwards looking for the first open slot
timeSlot = ensureSize(timeSlot, k);
for(var slot = k; slot >= 0; slot--) {
if (!timeSlot[slot]) {
// if found, schedule `i` there
timeSlot[slot] = task;
break;
}
}
// otherwise go to the next job (dump `i`)
}
return timeSlot;
}
@aybabtme
Copy link
Author

Silly task scheduling algorithm.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment