Skip to content

Instantly share code, notes, and snippets.

@ahmedengu
Last active November 28, 2016 18:46
Show Gist options
  • Save ahmedengu/76cc41f60db64e6bb4a9ca6a0b374d42 to your computer and use it in GitHub Desktop.
Save ahmedengu/76cc41f60db64e6bb4a9ca6a0b374d42 to your computer and use it in GitHub Desktop.
Design an efficient algorithm to solve the following scheduling problem. Provide a pseudocode and a worst case complexity analysis for your algorithm. You are given a set of n jobs with a processing time ti and a weight wi for each job. You want to order the jobs so as to minimize the weighted some of the completion times,   n i ii Cw 1 . Exam…
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.Vector;
public class SchedulingProblem {
static Vector<Integer> processTime = new Vector<>();
static Vector<Integer> processWeight = new Vector<>();
static SortedMap<Integer, Double> timeWeightRatio = new TreeMap<Integer, Double>() {
};
static int number = 2;
public static void main(String[] args) {
processTime.add(1);
processWeight.add(10);
processTime.add(3);
processWeight.add(2);
for (int i = 0; i < number; i++) { // O(N)
timeWeightRatio.put(i, processWeight.get(i) / (processTime.get(i) * 1.0)); // O(log(n))
}
// ------------ O(nlog(n))
int sum = 0, tmpTime = 0;
while (timeWeightRatio.size() > 0) { // O(n)
tmpTime += processTime.get(timeWeightRatio.firstKey()); // O(n)
sum += processWeight.get(timeWeightRatio.firstKey()) * tmpTime; // O(n)
System.out.print(processWeight.get(timeWeightRatio.firstKey()) + " * " + tmpTime + ((timeWeightRatio.size() > 1) ? " + " : " = " + sum));
timeWeightRatio.remove(timeWeightRatio.firstKey()); // O(log(n))
}
// >>>> O(nlog(n))
}
}
10 * 1 + 2 * 4 = 18
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment