Data Structures, Algorithms, & Applications in Java
Chapter 18, Exercise 11

(a)

To implement the greedy strategy, we first sort the tasks by task time using any n log n sorting algorithm, and then assign the tasks to the m persons in round-robin fashion. The task assignment takes linear time. So the overall complexity is O(n log n). The code for the ACT method is given below. A test program and output are given in the files AverageCompletionTime3.*.

---

public class AverageCompletionTime3
{
   // top-level nested class
   static class Task implements Comparable
   {
      // instance data members
      int time;                  // task length
      int id;                    // task id
      int person;                // person who is to do the task

      // constructor
      Task(int theTime, int theId)
      {
         time = theTime;
         id = theId;
      }

     // method of Comparable
     /** return true iff this < x */
     public int compareTo(Object x)
     {
        int xTime = ((Task) x).time;
        if (time < xTime)
           return -1;
        if (time == xTime)
           return 0;
        return 1;
      }

      /** return true iff this == x */
      public boolean equals(Object x)
         {return time == ((Task) x).time;}
   }

   /** reorder the tasks task[1:task.length-1] so that the
     * average completeion time is minimized
     * param m is the number of persons available to do tasks */
   public static void minimizeAverageCompletionTime(Task [] task, int m)
   {
      HeapSort.heapSort(task);
      // assign tasks to persons in round-robin fashion
      for (int i = 1; i <= task.length - 1; i++)
         task[i].person = (i-1) % m + 1;
   }
}

(b)

The greedy startegy implemented by method minimizeAverageCompletionTime always minimize the ACT. To see this, let the task times, in nondecreasing order, be t1, t2, ..., tn. The ACT of the task assignment constructed by the greedy algorithm is the sum of floor((n-i+1)/m)ti for i equal to 1 to n divided by n. In the sum, we see that the m largest times are multiplied by 1, the next m by 2, the next m by 3, etc. In every task assignment, the last task assigned to each person is multiplied by 1; the second last task by 2; etc. Therefore, we cannot get a smaller sum than obtained by the greedy algorithm.