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…

SchedulingProblem.java

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))
    }
}

ΙsampleOutput.txt

10 * 1 + 2 * 4 = 18