一个算法面试题，怎么写？ 第1页

这是一个很有趣也很常见的问题，但是很不幸的是，这个问题是NP-hard^[1]，也就是说除非 否则没有多项式时间算法。

但是我们可以用动态规划设计一个伪多项式的算法^[2] ，虽然也没有那么简单。当然，一个带剪枝的搜索算法，应该是很容易实现的，我想这应该也是这道面试题的初衷。

另外这篇review^[3] 总结了了很多这类工作安排问题的复杂度和算法，虽然都是些上世纪的研究，但也是很全面和深刻的。

参考

1. ^Du J, Leung J Y T. Minimizing total tardiness on one machine is NP-hard[J]. Mathematics of operations research, 1990, 15(3): 483-495. https://doi.org/10.1287/moor.15.3.483
2. ^Lawler E L. A “pseudopolynomial” algorithm for sequencing jobs to minimize total tardiness[M]//Annals of discrete Mathematics. Elsevier, 1977, 1: 331-342. https://www.sciencedirect.com/science/article/pii/S0167506008707428
3. ^A Review of Machine Scheduling: Complexity, Algorithms and Approximability https://link.springer.com/chapter/10.1007/978-1-4613-0303-9_25