Problem
Given N tasks and M task handlers. Each handler can finish a task with time t[i]. Distribute the tasks to the handlers, so that the total time spent on finishing the N tasks is minimum. For example, we have 5 tasks and 2 task handlers. handler 1 can finish one task in 5 minutes, while handler 2 can finish one task in 8 minutes. The optimum distribution will be:
handler1 handles 3 tasks and handler2 handles 2 tasks, the total time spent will be 16 minutes.
Solution
We can use greedy algorithm. The local minimum will be, for task i, find the handler which cause lowest finish time increase once taking this task, then assign the task to it.
public class OptimumDistro {
public static void bestDistro(int[] handlers, int numOfTasks) {
int m = handlers.length;
int[] optimum = new int[m];
int minTime = 0;
for(int i = 0; i < m; i++) {
optimum[i] = 0;
}
for(int n = 0; n < numOfTasks; n++) {
int chosenHandler = 0;
int finishTime = optimum[0] + handlers[0];
for(int i = 1; i < m; i++) {
int currFinishTime = optimum[i] + handlers[i];
if(currFinishTime < finishTime) {
finishTime = currFinishTime;
chosenHandler = i;
}
}
optimum[chosenHandler] += handlers[chosenHandler];
minTime = optimum[chosenHandler];
}
System.out.println(numOfTasks + " tasks finished in " + minTime);
System.out.println("task distribution:");
for(int i = 0; i < m; i++) {
System.out.println(optimum[i]/handlers[i] + " tasks is handled at unit speed " + handlers[i]);
}
}
public static void main(String...args) {
int[] handlers = new int[]{5, 8};
bestDistro(handlers, 5);
}
}
The time cost is O(NM) and space cost is O(M).
