多台打印机如何分配任务使总时间最短
哪些公司问过
答案要点
- 识别为多机调度,目标是最小化最大完成时间makespan
- 在线场景用列表调度:每个任务分给当前负载最小的机器
- 离线场景用LPT:按时长降序,再分给负载最小的机器
- 用最小堆维护各打印机累计时间,总复杂度O(n log n)
- 问题是NP难,LPT近似比为4/3-1/(3m);小规模可回溯求精确解
易错点
- 把目标理解成所有任务时间之和,和分配方式无关
- 以为贪心分配一定得到最优解,忽略NP难
- 离线场景不排序直接分配,大任务压在最后导致不均衡
面试官常见追问
- 如何求精确最优解?
- 如果目标是所有任务平均完成时间最短呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。