job.java

《算法设计与分析》王晓东编著

public class Job {
	
	public static int greedy(int []a,int m)
	{
		int n=a.length-1;
		int sum=0;
		if (n<=m) {
			for (int i=0;i<n;i++) sum+=a[i];
			System.out.println("为每个作业分配一台机器.");
			return sum;
		}
		JobNode [] d=new JobNode[n];
		for (int i=0;i<n;i++)
			d[i]=new JobNode(i+1,a[i+1]);
		MergeSort.mergeSort(d,0,d.length-1);
		MinHeap H=new MinHeap(m);
		for (int i=1;i<=m;i++) {
			MachineNode x=new MachineNode(i,0);
			H.put(x);
		}
		for (int i=n;i>=1;i--) {
			MachineNode x=(MachineNode)H.removeMin();
			System.out.println("将机器"+x.id+"从"+x.avail+"到"
					+(x.avail+d[i-1].time)+"的时间段分配给作业"+d[i-1].id);
			x.avail+=d[i-1].time;
			sum=x.avail;
			H.put(x);
		}
		return sum;
	}

	public static void main(String args[])
	{
		int[] a=new int[]{0,2,14,4,16,6,5,3};
		int m=3;
		
		System.out.println(greedy(a,m));	
	}
}