面试题库 › Java 后端 › 多台打印机如何分配任务使总时间最短

多台打印机如何分配任务使总时间最短

难度 ★★★在 1 场真实面经中被问到 方向:Java 后端考点:贪心与回溯

哪些公司问过

拼多多1

常见岗位:安卓

答案要点

  1. 识别为多机调度,目标是最小化最大完成时间makespan
  2. 在线场景用列表调度:每个任务分给当前负载最小的机器
  3. 离线场景用LPT:按时长降序,再分给负载最小的机器
  4. 用最小堆维护各打印机累计时间,总复杂度O(n log n)
  5. 问题是NP难,LPT近似比为4/3-1/(3m);小规模可回溯求精确解

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题