LeetCode 1335 - Minimum Difficulty of a Job Schedule

LeetCode Problem 1335

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem gives us an array jobDifficulty, where each element represents the difficulty of a job. The jobs must be completed in order, meaning you cannot rearrange them. If you want to work on job i, then every job before it must already be completed.

We must divide all jobs into exactly d consecutive groups, where each group represents the jobs completed in one day. Every day must contain at least one job.

The difficulty of a single day is defined as the maximum job difficulty among all jobs assigned to that day. The total schedule difficulty is the sum of the daily difficulties across all d days.

Our goal is to minimize this total difficulty.

For example, if:

jobDifficulty = [6,5,4,3,2,1]
d = 2

One valid schedule is:

• Day 1: [6,5,4,3,2], difficulty = 6
• Day 2: [1], difficulty = 1

Total difficulty = 6 + 1 = 7

This is optimal.

The constraints are important:

• jobDifficulty.length <= 300
• d <= 10

The relatively small value of d strongly suggests dynamic programming. A brute-force partitioning solution would grow exponentially and become infeasible.

One critical observation is that if the number of jobs is smaller than the number of days, the answer is impossible. Since each day must contain at least one job, we cannot schedule n jobs across more than n days.

Important edge cases include:

• len(jobDifficulty) < d, impossible schedule
• d == 1, all jobs must be completed in one day
• d == len(jobDifficulty), exactly one job per day
• Arrays with repeated values
• Arrays where optimal partitions are not obvious

Approaches

Brute Force

The brute-force solution tries every possible way to partition the jobs into d consecutive groups.

At every position, we can decide where the current day ends and recursively solve the remaining jobs for the remaining days. For each partition, we compute:

• The maximum difficulty for the current day
• The optimal difficulty for the remaining days

Then we take the minimum over all possibilities.

This approach is correct because it explores every valid schedule. However, the number of partitions grows exponentially. Even with memoization omitted, the solution becomes far too slow for n = 300.

Dynamic Programming

The key insight is that many recursive states repeat.

Suppose we define:

• dp[i][day] = minimum difficulty to schedule jobs starting from index i using exactly day remaining days

From a given state, we try all valid endings for the current day. While expanding the current day's jobs, we maintain the running maximum difficulty.

The transition becomes:

dp[i][day] =
    min over j:
        max(jobDifficulty[i..j]) + dp[j+1][day-1]

This avoids recomputing overlapping subproblems.

Since:

• n <= 300
• d <= 10

An O(n² × d) solution is efficient enough.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Explores every partition recursively
Optimal DP	O(d × n²)	O(d × n)	Memoized or tabulated dynamic programming

Algorithm Walkthrough

1. First, check whether scheduling is even possible.

If the number of jobs is smaller than the number of days, return -1. Every day must contain at least one job. 2. Define the DP state.

Let:

dp(day, index)

represent the minimum difficulty required to schedule jobs starting at index using exactly day remaining days. 3. Handle the base case.

If there is only one day left, then all remaining jobs must be completed on that day.

The difficulty becomes:

max(jobDifficulty[index:])

4. Try all valid partitions for the current day.

Suppose the current day ends at position j.

Then:

• Current day's difficulty is the maximum value in jobDifficulty[index:j+1]
• Remaining cost is dp(day - 1, j + 1)

We compute:

current_max + remaining_cost

and minimize over all choices. 5. Ensure enough jobs remain for future days.

If there are remaining_days left, we must leave at least one job per remaining day.

Therefore, the partition loop only goes up to:

n - remaining_days

6. Use memoization.

Many states repeat during recursion. Caching computed states prevents exponential recomputation. 7. Return the answer for:

dp(d, 0)

Why it works

The algorithm works because every valid schedule can be represented as a sequence of partition boundaries. For each state, we exhaustively consider every valid endpoint for the current day while recursively solving the remaining subproblem optimally.

The recurrence satisfies optimal substructure:

• An optimal full schedule must contain optimal schedules for its suffix subproblems.

Memoization guarantees each state is solved only once.

Python Solution

from typing import List
from functools import lru_cache

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)

        if n < d:
            return -1

        @lru_cache(None)
        def dp(index: int, days_left: int) -> int:
            if days_left == 1:
                return max(jobDifficulty[index:])

            current_max = 0
            best = float("inf")

            # Leave at least one job for each remaining day
            for j in range(index, n - days_left + 1):
                current_max = max(current_max, jobDifficulty[j])

                next_cost = dp(j + 1, days_left - 1)

                best = min(best, current_max + next_cost)

            return best

        return dp(0, d)

The implementation begins by checking whether scheduling is possible. If there are fewer jobs than days, the function immediately returns -1.

The recursive function dp(index, days_left) represents the minimum schedule difficulty starting from index with days_left remaining days.

The base case occurs when only one day remains. In that scenario, all remaining jobs must be completed together, so the difficulty is simply the maximum remaining job difficulty.

Inside the transition loop, we progressively extend the current day from index to j. The variable current_max tracks the maximum difficulty encountered so far, which avoids recomputing the maximum repeatedly.

For every possible partition, we recursively compute the optimal difficulty for the remaining jobs and combine it with the current day's difficulty.

Memoization via @lru_cache ensures each state is computed only once.

Go Solution

package main

import "math"

func minDifficulty(jobDifficulty []int, d int) int {
	n := len(jobDifficulty)

	if n < d {
		return -1
	}

	memo := make([][]int, n)

	for i := 0; i < n; i++ {
		memo[i] = make([]int, d+1)

		for j := 0; j <= d; j++ {
			memo[i][j] = -1
		}
	}

	var dp func(int, int) int

	dp = func(index int, daysLeft int) int {
		if daysLeft == 1 {
			maxVal := 0

			for i := index; i < n; i++ {
				if jobDifficulty[i] > maxVal {
					maxVal = jobDifficulty[i]
				}
			}

			return maxVal
		}

		if memo[index][daysLeft] != -1 {
			return memo[index][daysLeft]
		}

		currentMax := 0
		best := math.MaxInt32

		for j := index; j <= n-daysLeft; j++ {
			if jobDifficulty[j] > currentMax {
				currentMax = jobDifficulty[j]
			}

			nextCost := dp(j+1, daysLeft-1)

			if currentMax+nextCost < best {
				best = currentMax + nextCost
			}
		}

		memo[index][daysLeft] = best
		return best
	}

	return dp(0, d)
}

The Go implementation follows the same recursive dynamic programming structure as the Python version.

Since Go does not provide built-in memoization decorators like Python's lru_cache, we explicitly allocate a 2D memo table initialized with -1.

The recursive closure dp stores computed states in memo[index][daysLeft].

Go slices are used directly instead of Python lists. Integer overflow is not an issue here because the maximum possible answer is bounded by:

1000 × 300 = 300000

which easily fits inside a 32-bit integer.

Worked Examples

Example 1

jobDifficulty = [6,5,4,3,2,1]
d = 2

We compute:

dp(0, 2)

Possible partitions for Day 1:

Day 1 Jobs	Day 1 Max	Remaining Jobs	Remaining Cost	Total
[6]	6	[5,4,3,2,1]	5	11
[6,5]	6	[4,3,2,1]	4	10
[6,5,4]	6	[3,2,1]	3	9
[6,5,4,3]	6	[2,1]	2	8
[6,5,4,3,2]	6	[1]	1	7

Minimum = 7

Answer:

7

Example 2

jobDifficulty = [9,9,9]
d = 4

We have only 3 jobs but need 4 days.

Since every day requires at least one job:

3 < 4

Impossible.

Answer:

-1

Example 3

jobDifficulty = [1,1,1]
d = 3

Each day must contain exactly one job.

Day	Jobs	Difficulty
1	[1]	1
2	[1]	1
3	[1]	1

Total:

1 + 1 + 1 = 3

Answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(d × n²)	There are O(d × n) states, each exploring O(n) transitions
Space	O(d × n)	Memoization table stores one value per state

The dynamic programming solution computes each (index, days_left) state once. For each state, we iterate through all possible partition endpoints. Since there are at most n × d states and each performs up to n transitions, the total time complexity is O(d × n²).

The memoization cache stores all states, producing O(d × n) space complexity.

Test Cases

from typing import List

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        from functools import lru_cache

        n = len(jobDifficulty)

        if n < d:
            return -1

        @lru_cache(None)
        def dp(index: int, days_left: int) -> int:
            if days_left == 1:
                return max(jobDifficulty[index:])

            current_max = 0
            best = float("inf")

            for j in range(index, n - days_left + 1):
                current_max = max(current_max, jobDifficulty[j])
                best = min(best, current_max + dp(j + 1, days_left - 1))

            return best

        return dp(0, d)

sol = Solution()

assert sol.minDifficulty([6,5,4,3,2,1], 2) == 7  # provided example
assert sol.minDifficulty([9,9,9], 4) == -1  # impossible schedule
assert sol.minDifficulty([1,1,1], 3) == 3  # one job per day

assert sol.minDifficulty([7], 1) == 7  # single job
assert sol.minDifficulty([1,2,3,4,5], 1) == 5  # all jobs in one day
assert sol.minDifficulty([1,2,3,4,5], 5) == 15  # one job each day

assert sol.minDifficulty([11,111,22,222,33,333,44,444], 6) == 843  # mixed values

assert sol.minDifficulty([5,5,5,5], 2) == 10  # repeated difficulties

assert sol.minDifficulty([10,1,10,1,10], 3) == 21  # nontrivial partitioning

assert sol.minDifficulty([0,0,0], 2) == 0  # zero difficulties

assert sol.minDifficulty([1,100,1,100,1], 2) == 101  # optimal split selection

Test	Why
[6,5,4,3,2,1], d=2	Validates standard partition optimization
[9,9,9], d=4	Validates impossible scheduling
[1,1,1], d=3	Tests one job per day
[7], d=1	Smallest valid input
[1,2,3,4,5], d=1	All jobs in one day
[1,2,3,4,5], d=5	Every day gets one job
Mixed large values	Tests DP correctness under uneven distributions
Repeated values	Ensures repeated maxima handled correctly
Alternating high and low values	Tests partition decision quality
Zero difficulties	Ensures zeros handled properly
Multiple optimal split possibilities	Verifies global optimum selection

Edge Cases

One important edge case occurs when there are fewer jobs than days. Since every day must contain at least one job, scheduling becomes impossible. A naive implementation might still attempt recursion or DP construction and produce invalid states. The implementation handles this immediately with:

if n < d:
    return -1

Another important case is when only one day remains. In that situation, all remaining jobs must be completed together. A common mistake is continuing to recurse unnecessarily or partitioning further. The implementation correctly collapses the remainder into a single day by returning:

max(jobDifficulty[index:])

A third tricky case occurs when d == len(jobDifficulty). Every day must receive exactly one job, so the answer becomes the sum of all job difficulties. Some incorrect implementations accidentally allow empty days or invalid partitions. The loop bounds in this solution guarantee that enough jobs remain for future days:

for j in range(index, n - days_left + 1):

This constraint ensures every recursive branch corresponds to a valid schedule.