Batch system

During last SRM one f the problem was to solve task of scheduling jobs for hypothetical computer. In short there are several tasks from many people. Each individual can have possibly many tasks. Of course each task has his own duration. The aim is to schedule the jobs in such a way that the average waiting time over all users is minimized.

This problem reminded me Joel’s article about Human Task Switches. This is no surprise that you can solve problem stated in SRM using greedy algorithm. The most significant observation you have to do is that regardless of arrangement of jobs all of them will be done after the sum of their durations. So, you put the longest at the end to give the rest of jobs a change to finish earlier. You can iterate that way until no job left. In other words you have to sort you jobs by duration.

Of course in problem posted you have to make little extra work to join all users jobs, a handle properly some corner situations. But, solution still remains simple with significant consequences. If you care about average finishing time of your tasks, you should never, ever switch your tasks. Not to mention that these switches have high impact on your productivity. Time needed to focus on new task and obtain full productivity is not insignificant.

There are some slight modifications of this problems, when you interested in partial results or tasks have priorities. Partial results appears where others are not necessary waiting for your whole job, but partial work is also well welcomed (ex. milestones during whole project). Priorities appears always when your lead thinks that problem you already solving is not substantial, and he assign you more proper job.

Code that can be used to solve problem in SRM below.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

class Group implements Comparable<Group> {
 public Long sum = 0L;
 public Long min = Long.MAX_VALUE;
 public PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

 public void add(int pos, int val) {
  sum += val;
  min = Math.min(pos, min);
  pq.add(pos);
 }

 public int compareTo(Group o) {
  if (sum < o.sum) return -1;
  else if (sum > o.sum) return 1;
  else return min.compareTo(o.min);
 }
}

public class BatchSystem 
{
 public int[] schedule(int[] duration, String[] user) {
  Set<String> set 
      = new HashSet<String>(Arrays.asList(user));
  Map<String, Group> map = new HashMap<String, Group>();
  for (String string : set)
   map.put(string, new Group());

  for (int i = 0; i < user.length; ++i)
   map.get(user[i]).add(i, duration[i]);

  List<Group> list = new ArrayList<Group>(map.values());
  Collections.sort(list);

  int[] res = new int[duration.length];
  int index = 0;
  for (Group g : list) 
   for (int i : g.pq) 
    res[index++] = i;
   
  return res;
 }
}