#1335
Minimum Difficulty of a Job Schedule
expert · 1195 · lc hard +32 · verified · 59.7% accepted · 3,591 likes · top 58%
Description
You need to schedule all jobs over d days. Jobs must be completed in the given order (job i can only begin after jobs 0 through i-1 are done), and each day must contain at least one job. The cost of a day equals the maximum difficulty among its jobs; the total schedule cost is the sum of all daily costs.
Given jobDifficulty (where jobDifficulty[i] is the difficulty of the ith job) and the integer d, return the minimum possible total schedule cost, or -1 if no valid schedule exists.
Example 1:
Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7
Example 2:
Input: jobDifficulty = [9,9,9], d = 4
Output: -1
Explanation: If you finish a job per day you will still have a free day. you cannot find a schedule for the given jobs.
Example 3:
Input: jobDifficulty = [1,1,1], d = 3
Output: 3
Explanation: The schedule is one job per day. total difficulty will be 3.
Code
1
2
3