Minimum Difficulty of a Job Schedule

Minimum Difficulty of a Job Schedule is a classic interval-partition DP. You must split an ordered list of jobs into exactly d days, and the goal is to make the sum of each day's hardest job as small as possible.

The slow way first

Each day eats a contiguous block of jobs (because jobs run in order), so a schedule is really a choice of where to cut. With d days you place d - 1 cuts among the jobs. Brute-forcing every placement of those cuts is exponential — far too slow once the array grows.

The question to ask: given that I have already placed some days, does my next choice depend on anything except where I currently am and how many days are left? It does not. That smells like dynamic programming.

The idea: split point + max of the last day

Think about the last day. It takes some contiguous suffix jobs[j..i], and its cost is max(jobs[j..i]). Everything before it — jobs[0..j-1] — must be packed into d - 1 days, which is the same problem one size smaller.

So define dp[d][i] = the cheapest way to schedule jobs[0..i] in d days. Then:

dp[d][i] = min over j of ( dp[d-1][j-1] + max(jobs[j..i]) )

We slide the split j, keep a running max of the last day, and add the best solution to the prefix.

The key insight: as the last day's left edge j moves left, it can only swallow more jobs, so its max only grows — we update it in O(1) while scanning.

Walk through it

Step through the animation. The split pointer marks where the last day begins. For jobs = [6,5,4,3,2,1] and d = 2, we try each cut: cutting early leaves the hard jobs sharing a day (total 11), and cutting late isolates a single easy job on the last day. Because day 1 already contains the 6, its cost is stuck at 6 no matter what — so the win comes from making day 2 as cheap as possible: just [1], for a total of 7.

Pseudocode

n = number of jobs
if n < d: return -1            # cannot give every day a job
define solve(i, days):         # min cost for jobs[0..i] in "days" days
    run_max = 0
    best = infinity
    for j from i down to days-1:        # last day starts at j
        run_max = max(run_max, jobs[j]) # last day's hardest job
        if days == 1: rest = 0          # no prefix left
        else:         rest = solve(j-1, days-1)
        best = min(best, run_max + rest)
    return best
return solve(n-1, d)

The Python solution

def min_difficulty(jobs, d):
    n = len(jobs)
    if n < d:
        return -1
    INF = float('inf')
    # dp[k][i] = min cost to schedule jobs[:i+1] in k days
    def solve(i, days):
        run_max = 0
        best = INF
        for j in range(i, days - 2, -1):
            run_max = max(run_max, jobs[j])
            rest = 0 if days == 1 else solve(j - 1, days - 1)
            best = min(best, run_max + rest)
        return best
    return solve(n - 1, d)

• if n < d is the impossibility guard: with fewer jobs than days, some day would be empty.
• solve(i, days) answers: cheapest way to do jobs[0..i] in days days.
• The loop slides j, the start of the last day, from i leftward; it must stop early enough to leave one job for each remaining day (days - 1).
• run_max is the last day's difficulty — its hardest job — updated in O(1) as the day grows.
• rest is the best schedule for everything before the cut, solved recursively with one fewer day.
• We keep the smallest run_max + rest over all cuts. Memoizing solve on (i, days) turns the exponential search into a polynomial DP.

Complexity

There are n * d distinct states, and each scans up to n split points, giving O(n² * d) time. The memo table holds one value per state, so O(n * d) space.

When this pattern shows up

Practice