1335. Minimum Difficulty of a Job Schedule¶
题目信息¶
- 题号:
1335
- 难度:
Hard
- 主题:
动态规划、连续分段、任务调度
- 原题:
- 重点:
工作必须按原顺序完成并分配到恰好
d天,每天至少一项;每天难度为当天最大工作难度
题目重述¶
给定工作难度数组 jobDifficulty 和天数 d。工作必须按数组顺序完成;只有前面的工作完成后才能开始后面的工作。需要把所有工作划分到恰好 d 个连续非空分段。
每天的难度是该天工作难度的最大值,总难度是各天难度之和。返回最小总难度;若工作数少于天数,返回 -1。
1 <= jobDifficulty.length <= 300,1 <= d <= 10。
自建示例¶
最后一天只安排较容易的末尾工作可能最优:
输入:jobDifficulty = [6,3,5,2], d = 2
输出:8
解释:前三项安排在第一天,难度为 6;最后一项第二天完成,难度为 2。
工作数不足以保证每天一项时无解:
输入:jobDifficulty = [4,2], d = 3
输出:-1
解释:无法把两项工作分配到三个非空工作日。