Solution for problem BatchSystem, used in Single Round Match 481 Round 1 - Division II, Level Three

BatchSystem.java

package topcoder;

import java.util.*;

/**
 * Problem statement:
 * http://community.topcoder.com/stat?c=problem_statement&pm=10808&rd=14234
 * 
 * I used permutation code from:
 * http://www.cs.utexas.edu/users/djimenez/utsa/cs3343/lecture25.html
 */
public class BatchSystem
{
	int[] answer;
	double min;
	
	class Job {
		int index, time;
		String user;
		Job(int i,int t,String u) {
			index=i;time=t;user=u;
		}
	}
	
	int[] schedule(int[] duration, String[] user)
	{
		int n	= duration.length;
		answer	= new int[n];
		Arrays.fill(answer, Integer.MAX_VALUE);
		Job[] jobs	= new Job[n];
		min		= Double.MAX_VALUE;
		
		for(int i = 0; i < n; i++) {
			jobs[i] = new Job(i, duration[i], user[i]);
		}
		
		perm(jobs, n, 0);
		
		return answer;
	}	
	
	void perm(Job v[], int n, int i)
	{
		int j;
		
		if(i == n)
		{
			int time = 0;
			TreeMap<String,Integer> times = new TreeMap<>();
			for(j=0; j<n; j++)
			{
				times.put(v[j].user, time + v[j].time);				
				time += v[j].time;
			}
			
			double sum = 0;
			for(Map.Entry<String,Integer> e : times.entrySet()) sum += e.getValue();
			double average = sum / times.size();
			
			// compare lexicographically
			if(average == min) {
				boolean needToChange = false;
				for(j=0; j<n; j++) {
					if(v[j].index < answer[j]) {
						needToChange = true;
						break;
					} else if(v[j].index > answer[j]) {
						break;
					}
				}				
				if(needToChange) for(j=0; j<n; j++) answer[j] = v[j].index;
			}
			if(average < min) {
				for(j=0; j<n; j++) answer[j] = v[j].index;
				min = average;
			}
		}
		else
		{
			for(j=i; j<n; j++)
			{
				swap(v, i, j);
				perm(v, n, i+1);				
				swap(v, i, j);
			}
		}
	}
	
	void swap(Job[] v, int i, int j)
	{
		Job t = v[i];
		v[i] = v[j];
		v[j] = t;
	}
	
	public static void main(String[] args)
	{
		BatchSystem bs = new BatchSystem();
		
		int[] idxs;
		
		idxs = bs.schedule(
				new int[]{200, 200, 200},
				new String[]{"Gil", "Sarah", "Warrick"});		
		printArray(idxs);
		
		idxs = bs.schedule(
			new int[]{400, 100, 100, 100},
			new String[]{"Danny Messer", "Stella Bonasera", "Stella Bonasera", "Mac Taylor"});
		printArray(idxs);
		
		idxs = bs.schedule(
			new int[]{100, 200, 50},
			new String[]{"Horatio Caine", "horatio caine", "YEAAAAAAH"});			
		printArray(idxs);
	}
	
	static void printArray(int[] a) {
		for(int i=0; i<a.length; i++)
			System.out.print(" " + a[i]);
		System.out.println();
	}
}