Minimum Difficulty of a Job Schedule

Complete all jobs in jobDifficulty in their given order over exactly d days. Every day must contain at least one job. The difficulty for a day is the largest job difficulty assigned to it, and the total schedule difficulty is the sum of the daily difficulties. Return the minimum possible total, or -1 if no valid schedule exists.

Example 1:

Minimum Difficulty of a Job Schedule, example 1: illustration of the example

Input: jobDifficulty = [4,2,1]
d = 2

Output: 5

Explanation: Assign [4,2] to day 1 and [1] to day 2, for difficulty 4 + 1 = 5. The other possible split gives 4 + 2 = 6.

Example 2:

Minimum Difficulty of a Job Schedule, example 2: illustration of the example

Input: jobDifficulty = [2,5]
d = 3

Output: -1

Explanation: There are only two jobs, but every one of the three days needs a job. No valid schedule exists.

Example 3:

Minimum Difficulty of a Job Schedule, example 3: illustration of the example

Input: jobDifficulty = [0,0,0]
d = 2

Output: 0

Explanation: Split the three zero-difficulty jobs between two nonempty days. Each daily maximum is 0, so the total is 0.

Constraints:

1 <= jobDifficulty.length <= 300
0 <= jobDifficulty[i] <= 1000
1 <= d <= 10

Topics

Array Dynamic Programming

Company Tags

Please upgrade to NeetCode Pro to view company tags.