Abstract / Summary

Assign jobs to d days to minimize the highest day's difficulty sum.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 60% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of partitioning a sequence of job difficulties into a given number of days while minimizing the total difficulty. The difficulty of a single day is defined as the maximum difficulty among the jobs scheduled for that day, and the total difficulty is the sum of daily difficulties. The algorithm uses depth-first recursion with memoization to explore feasible partitions and prune impossible configurations.

Core Logic

The function begins by recording the number of jobs and defining a sentinel value that represents an invalid schedule.

jobs    = len(jobDifficulty)
invalid = float("inf")

A nested helper function deeper is decorated with @cache, which automatically stores results for each pair of arguments (done, days). This memoization prevents repeated evaluation of identical sub-problems.

@cache
def deeper(done, days):
    ...

The first base case handles the situation where no days remain. If all jobs have already been assigned (done == jobs) the function returns zero, indicating no additional difficulty. Otherwise it returns the sentinel invalid to signal that the schedule cannot be completed.

if days == 0:
    return 0 if done == jobs else invalid

The second base case checks whether the remaining number of jobs is insufficient to fill the remaining days without leaving idle days. If the number of jobs left (jobs - done) is less than the number of days left, the function returns invalid.

if done + days > jobs:
    return invalid   # prevent idle days

A third base case captures the scenario where all jobs have already been scheduled before exhausting the allotted days. In this case the remaining days contribute no additional difficulty, so the function returns zero.

if done == jobs:
    return 0

The main loop iterates over possible cut points for the current day. The loop variable i marks the last job assigned to the current day. The loop range stops early enough to guarantee that at least one job remains for each of the remaining days.

best = invalid
have = 0
for i in range(done, jobs - days + 1):
    have = max(have, jobDifficulty[i])
    best = min(best, have + deeper(i + 1, days - 1))

Inside the loop, have tracks the maximum difficulty encountered so far for the current day. The expression have + deeper(i + 1, days - 1) computes the total difficulty if the current day ends at job i and the remaining days are solved recursively. The variable best retains the smallest total difficulty found across all possible cut points.

Finally, the helper returns the best difficulty for the current state.

return best

The outer function invokes the helper with the initial state (no jobs done and d days available) and translates the sentinel value back to -1 when no feasible schedule exists.

result = deeper(0, d)
return -1 if result == invalid else result

Edge Cases Handled

The implementation explicitly addresses several boundary conditions:

• When the number of days requested exceeds the number of jobs, the condition done + days > jobs triggers early and returns invalid. This prevents schedules that would require idle days.
• When the job list is empty and the day count is zero, the base case days == 0 together with done == jobs yields a total difficulty of zero.
• When all jobs are assigned before the day counter reaches zero, the check if done == jobs returns zero, allowing the algorithm to gracefully handle extra days that would otherwise be idle.
• The loop limit jobs - days + 1 guarantees that each recursive call receives at least one job for every remaining day, thereby avoiding out-of-range indexing and ensuring that every day receives a non-empty segment.

Performance Optimizations

Memoization via @cache is the primary optimization. By caching the result of deeper(done, days) for each distinct pair of arguments, the algorithm avoids recomputing identical sub-problems that arise from different partition choices. This dramatically reduces the exponential blow-up typical of naïve recursive partitioning.

The loop range range(done, jobs - days + 1) is deliberately constrained. By stopping at jobs - days + 1, the algorithm eliminates iterations that would leave insufficient jobs for the remaining days, thereby pruning the search space without additional checks inside the loop.

The variable have is updated incrementally with max(have, jobDifficulty[i]). This avoids recomputing the maximum of the current segment on each iteration, turning what could be an O(n) operation per loop into O(1) incremental work.

Returning the sentinel invalid as float("inf") enables the use of min and max functions without extra conditional logic, keeping the inner loop tight and efficient.

Overall Flow

The function starts by establishing the problem size and an invalid marker. It defines a memoized recursive helper that evaluates the minimum difficulty for any prefix of jobs and a remaining day count. Base cases quickly resolve trivial or impossible states. The core loop iterates over feasible end points for the current day, maintaining the maximum difficulty for that day and combining it with the optimal solution for the remainder. After exploring all partitions, the helper returns the best total difficulty for the current state. The outer call initiates the process from the start of the job list with the full day budget, and the final result is either the computed minimum difficulty or -1 if no valid schedule exists.

Imagine you have a big pile of fun chores to finish over several days. Some chores are very easy and others are quite hard. You want to make sure you do all of them, but you also want to plan your schedule so the hardest chore you do each day makes the whole week feel as smooth as possible.

The code starts by counting how many chores are in the pile. There is a special tool called a cache that helps the computer remember the work it has already looked at so it does not have to do the same thinking twice.

The part called deeper is like a daydream where the code imagines different ways to split the chores across the days. It checks a few rules to stay on track. If there are no days left but some chores are still unfinished, that plan is tossed aside because it would not work. If there are more days left than chores to do, it also tosses that plan aside because every single day must at least have one chore to do.

When the code looks at a chore, it keeps track of how difficult that task is. It picks the hardest chore of the current day and keeps that number in its pocket. Then, it talks to its future self to see how to handle the rest of the work on the following days. By looking at all the different ways to group the chores, it figures out the best way to keep those hardest chores as small as possible. Finally, it looks at all its notes to find the single best plan for the whole week.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Java	C++				Python	TS
	WalkCCC	Java	C++				Python
	leetcode.ca	Java	C++			Go	Python	TS
	MemoryLimitExceeded		C++				Python
	Progiez	Java	C++				Python
github	black-shadows		C++
	charles-wangkai	Java
	everthis			JS
	gouthampradhan	Java
	JoshCrozier			JS
	lzl124631x		C++
	suxrobGM				C#
	varunu28	Java
	vthwang	Java
	wisdompeak		C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
gouthampradhan	Java
JoshCrozier	JavaScript
lzl124631x	C++
suxrobGM	C#
varunu28	Java
vthwang	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality