Minimum Difficulty of a Job Schedule
You want to schedule a list of jobs in d days. Jobs are dependent: to work on the i^th job, you have to finish all jobs j where 0 <= j < i.
You have to finish at least one task every day. The difficulty of a job schedule is the sum of the difficulties of each day of the d days. The difficulty of a day is the maximum difficulty of a job done on that day.
You are given an integer array jobDifficulty and an integer d. The difficulty of the i^th job is jobDifficulty[i].
Return the minimum difficulty of a job schedule. If you cannot find a schedule for the jobs, return -1.
Example 1
Input
jobDifficulty = [6,5,4,3,2,1], d = 2Output
7First day you can finish the first 5 jobs with difficulty 6, and the second day you can finish the last job with difficulty 1, so the total difficulty is 7.
Example 2
Input
jobDifficulty = [9,9,9], d = 4Output
-1Even if you finish one job per day, there will still be a free day, so no valid schedule exists.
Constraints
- 1 <= jobDifficulty.length <= 300
- 0 <= jobDifficulty[i] <= 1000
- 1 <= d <= 10
Asked at 7 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.