Show problems as
Classic problem #1335HardArrayDynamic Programming

Minimum Difficulty of a Job Schedule

Real-world version: Cheapest Shift Plan For A Restoration Queue
Tracked in this browser only
Read Minimum Difficulty of a Job Schedule on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A film archive restores reels in a fixed queue order. jobDifficulty[i] is the wear rating of the reel at position i, and the queue must be handled in exactly d shifts.

A shift takes a contiguous run of reels from the front of what is left, and every shift has to take at least one reel. The technician on a shift is billed for the single worst reel they touched, so a shift costs the largest wear rating inside its run. The bill for the whole plan is the sum over the d shifts.

Return the smallest possible bill. If the queue cannot be cut into d non-empty runs at all, return -1.

Examples

Example 1

Input
jobDifficulty = [4, 1, 9, 2], d = 2
Output
11

The plan [4, 1, 9] then [2] uses two contiguous non-empty runs and is billed 9 + 2 = 11.

Example 2

Input
jobDifficulty = [7, 3, 5, 8, 2], d = 3
Output
17

The plan [7], [3, 5, 8], [2] is billed 7 + 8 + 2 = 17, and each of its three runs is non-empty and contiguous.

Example 3

Input
jobDifficulty = [6, 2], d = 3
Output
-1

Only two reels are queued, so three non-empty runs cannot be formed and the sentinel is returned.

Example 4

Input
jobDifficulty = [5, 5, 5], d = 3
Output
15

Each shift must take exactly one reel and every reel is rated 5, so the bill is 5 + 5 + 5.

Constraints

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

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def cheapest_shift_plan(reels: list[int], shifts: int) -> int:
Java
public int cheapestShiftPlan(int[] reels, int shifts)

More on the same topics