|
多机调度
问题描述算法分析代码实现
问题描述
有n台规格一样的机器同时工作，有m个零件需要加工，第 i个零件加工时间为 ti，请你计算出加工完这批零件最少需要多少时间。
算法分析
当 mn 时
首先将零件按照加工时间排序，每次分配都将最长加工时间的零件，分配给当前总加工时间最短的机器，这样便是最优选择。如果我们每次是将需要处理时间最短的作业分配给空闲的机器，那么可能就会出现其它所有作业都处理完了只剩所需时间最长的作业在处理的情况，这样势必效率较低。
代码实现
Java中提供的优先队列 PriorityQueue 可以很好为我们提供方便。具体请参考一下 OJ题目 及实现代码。
输入： 第一行为两个整数n,m。n表示机器数，m表示零件数（1
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
// 创建优先队列，参数是 Machine类，自定义排序
PriorityQueue queue = new PriorityQueue((o1, o2)->o1.time-o2.time);
for (int i = 0; i
x[i] = sc.nextInt();
}
// 将零件升序排序
Arrays.sort(x);
// 遍历
for (int i = m-1; i >= 0; i--) {
Machine m1 = queue.poll();
m1.time += x[i];
queue.offer(m1);
}
// 输出最大的time，即队列尾部的 Machine.time
for (int i = 0; i |