Minimum Difficulty of a Job Schedule
Hard · Dynamic Programming · Array · Dynamic Programming
Problem
You must schedule a list of jobs over exactly d days. The jobs depend on each other, so they must be done in the given order: job i can start only after every job before it is finished. Each day you must finish at least one job.
jobDifficulty[i] is the difficulty of job i. A day’s difficulty is the largest difficulty among the jobs done that day, and a schedule’s difficulty is the sum over all d days.
Return the minimum difficulty of a valid schedule, or -1 if no schedule exists.
Examples
Input: jobDifficulty = [3,1,8,2], d = 2 Output: 10
Do jobs 3, 1 and 8 on day one (8) and job 2 on day two (2): 10. Putting the 8 with the 2 instead costs 3 + 8 = 11.
Input: jobDifficulty = [5,5], d = 3 Output: -1
Two jobs cannot fill three days.
Input: jobDifficulty = [2,4,1], d = 3 Output: 7
Three jobs in three days leaves one job per day: 2 + 4 + 1 = 7.
Constraints
- 1 <= len(jobDifficulty) <= 300
- 0 <= jobDifficulty[i] <= 1000
- 1 <= d <= 10
Approaches
- Baseline: try every way to cut the list — time O(C(n - 1, d - 1) · n), space O(d) for the recursion
Follow-up
A monotonic stack brings each day’s layer down to O(n): for a fixed number of days, the best value for prefix i can reuse the work of the nearest earlier job that is harder than job i - 1, for O(n·d) overall. See the use cases for blocks of bounded length worth their maximum, and for days that cost their spread.
Related problems
Start free on Cariara · Coding problems · System design studio
