【华为OD机考真题】流水线调度 · 最短完工时间 (Java/Go)

一、题目题目描述一个工厂有 m 条流水线来并行完成 n 个独立的作业该工厂设置了一个调度系统在安排作业时总是优先执行处理时间最短的作业。现给定流水线个数 m需要完成的作业数 n每个作业的处理时间分别为 t1, t2 ... tn。请你编程计算处理完所有作业的耗时为多少当 n m 时首先处理时间短的 m 个作业进入流水线其他的等待当某个作业完成时依次从剩余作业中取处理时间最短的进入处理。输入描述第一行为 2 个整数采用空格分隔分别表示流水线个数 m 和作业数 n第二行输入 n 个整数采用空格分隔表示每个作业的处理时长 t1, t2 ... tn。0 m, n 1000 t1, t2 ... tn 100注保证输入都是合法的。输出描述输出处理完所有作业的总时长示例输入3 58 4 3 2 10输出13说明先安排时间为 2、3、4 的 3 个作业。第一条流水线先完成作业时间 2然后调度剩余时间最短的作业 8。第二条流水线完成作业时间 3然后调度剩余时间最短的作业 10。总工时就是第二条流水线完成作业的时间 133 10。二、解题思路贪心 最小堆模拟1. 核心逻辑这道题是一个典型的贪心算法结合优先队列的问题。贪心策略为了让总时间最短必须让忙碌的流水线尽早空闲下来去接新的活。因此总是把新任务交给当前预计完成时间最早的那条流水线。同时任务本身也要按从小到大的顺序处理确保短任务优先被消化。数据结构我们需要一个数据结构来维护 mm 条流水线的当前完成时间并能快速取出最小值。这正是最小堆Min-Heap的用武之地。2. 算法步骤排序将 n 个作业时长数组tasks从小到大排序。初始化堆如果 n≤m 直接返回最大的那个作业时长因为可以并行同时做。如果 nm 将前 m 个作业的时长放入最小堆中代表 m 条流水线目前的完工时间。模拟调度遍历剩余的 n−m 个作业。每次从堆顶弹出最小值min_time代表最早空闲的流水线时刻。将该时刻加上当前作业时长task得到新的完工时间new_time min_time task。将new_time重新推入堆中。获取结果当所有作业都分配完毕后堆中存储的是每条流水线的最终完工时间。答案即为堆中的最大值。技巧在 Go/Java 中堆弹空后的最后一个元素或者遍历堆数组找最大值即可。其实更简单的逻辑是最后一次弹出的min_time加上对应的task并不一定是最大值必须遍历堆中所有元素取最大值或者在循环结束后不断弹出堆直到只剩一个最大值不推荐破坏结构最直接的方法是遍历堆底层数组找最大。3. 复杂度分析时间复杂度排序 O(Nlog⁡N) 。堆操作共进行 N−m 次入堆和出堆每次 O(log⁡M) 。总复杂度 O(Nlog⁡NNlog⁡M) 。鉴于 N,M100 效率极高。空间复杂度 O(M) 用于存储堆。三、代码实现1. Java 实现Java 拥有强大的标准库java.util.PriorityQueue默认就是最小堆实现非常简洁。import java.util.Arrays; import java.util.PriorityQueue; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); // 读取 m 和 n if (!scanner.hasNextInt()) return; int m scanner.nextInt(); int n scanner.nextInt(); int[] tasks new int[n]; for (int i 0; i n; i) { tasks[i] scanner.nextInt(); } // 1. 贪心先对作业时长排序 Arrays.sort(tasks); // 特殊情况如果作业数少于等于流水线数耗时就是最长的那个作业 if (n m) { System.out.println(tasks[n - 1]); return; } // 2. 初始化最小堆存储每条流水线的“当前完成时间” // Java PriorityQueue 默认是最小堆 PriorityQueueInteger pq new PriorityQueue(); // 先将前 m 个作业分配给 m 条流水线 for (int i 0; i m; i) { pq.offer(tasks[i]); } // 3. 模拟调度过程 for (int i m; i n; i) { // 取出最早完成的流水线时间 int earliestFinishTime pq.poll(); // 将当前最短作业分配给它计算新的完成时间 int newFinishTime earliestFinishTime tasks[i]; // 放回堆中 pq.offer(newFinishTime); } // 4. 结果是所有流水线完成时间的最大值 // 此时堆中可能有多个元素需要遍历找最大值 int maxTime 0; for (int time : pq) { if (time maxTime) { maxTime time; } } System.out.println(maxTime); scanner.close(); } }2. Go 实现Go 的标准库container/heap需要用户实现heap.Interface接口。虽然稍微繁琐一点但能让我们更深入理解堆的底层运作且性能极佳。package main import ( container/heap fmt sort ) // IntHeap 定义一个最小堆类型 type IntHeap []int // 实现 heap.Interface 接口的五个方法 func (h IntHeap) Len() int { return len(h) } func (h IntHeap) Less(i, j int) bool { return h[i] h[j] } // 最小堆小的在上面 func (h IntHeap) Swap(i, j int) { h[i], h[j] h[j], h[i] } func (h *IntHeap) Push(x interface{}) { *h append(*h, x.(int)) } func (h *IntHeap) Pop() interface{} { old : *h n : len(old) x : old[n-1] *h old[0 : n-1] return x } func solve() { var m, n int if _, err : fmt.Scan(m, n); err ! nil { return } tasks : make([]int, n) for i : 0; i n; i { fmt.Scan(tasks[i]) } // 1. 贪心排序 sort.Ints(tasks) // 特殊情况 if n m { fmt.Println(tasks[n-1]) return } // 2. 初始化堆 h : IntHeap{} heap.Init(h) // 放入前 m 个作业 for i : 0; i m; i { heap.Push(h, tasks[i]) } // 3. 模拟调度 for i : m; i n; i { // 弹出最小值最早完成的流水线时间 earliest : heap.Pop(h).(int) // 加上新作业时间 newTime : earliest tasks[i] // 推回堆 heap.Push(h, newTime) } // 4. 找最大值 maxTime : 0 for _, t : range *h { if t maxTime { maxTime t } } fmt.Println(maxTime) } func main() { solve() }四、关键点深度解析1. 为什么必须先排序作业题目明确要求“总是优先执行处理时间最短的作业”。如果不排序直接按输入顺序分配可能会导致长作业阻塞了流水线而短作业在后面等待违背了题目的调度规则。排序保证了我们每次取出的tasks[i]都是当前剩余任务中最小的符合贪心策略。2. 为什么用最小堆维护流水线时间我们的目标是找到“谁最先闲着”。数组遍历找最小值是 O(M) 而堆顶取值是 O(1) 调整堆是 O(log⁡M) 。在 N 较大时堆的优势非常明显。本题虽然 N,M100 数据量小但在机考中养成使用合适数据结构的习惯至关重要。3. 结果为何是堆中的最大值堆中存储的是每条流水线最终的任务完成时刻。整个工厂完工取决于最慢的那条流水线。注意堆顶是最小值最早完成的所以不能直接Pop出来当结果必须遍历堆内所有元素取Max。4. 边界情况处理n≤m作业比流水线少或刚好够分。此时所有作业同时开始总耗时就是单个作业中最长的那个排序后的最后一个。代码中做了特判避免逻辑复杂化。输入合法性题目保证合法实际工程中可增加对 m0 等的防御性编程。五、总结与建议这道题是“多机调度问题”的一个简化变种带有特定贪心规则。思维转换将物理世界的“流水线空闲”抽象为数字世界中的“最小值弹出”。语言特性Java利用PriorityQueue可以快速写出生产级代码适合追求开发效率的场景。Go通过实现heap.Interface展示了 Go 接口组合的灵活性适合对性能和底层控制有要求的场景。给考生的建议熟记模板Java 的PriorityQueue用法和 Go 的heap接口实现模板要烂熟于心。审题细节注意题目中的“优先执行短作业”是指任务队列的排序而“空闲即插”是指资源的分配策略两者结合才是正解。结果提取千万不要以为堆顶就是答案对于“完工时间”类问题答案往往是集合中的最大值。掌握这种“排序 优先队列模拟”的模式你可以轻松解决类似的资源分配、任务调度、甚至哈夫曼编码构造等问题