Minimum Difficulty of a Job Schedule - Practice Coding Problems

Minimum Difficulty of a Job Schedule - Problem

You want to schedule a list of jobs in d days. Jobs are dependent (i.e., to work on the i-th job, you have to finish all jobs j where 0 <= j < i).

You have to finish at least one task every day. The difficulty of a job schedule is the sum of difficulties of each day of the d days. The difficulty of a day is the maximum difficulty of a job done on that day.

Given an integer array jobDifficulty and an integer d, return the minimum difficulty of a job schedule. If you cannot find a schedule for the jobs, return -1.

Input & Output

Example 1 — Basic Case

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

› Output: 7

💡 Note: Optimal schedule: Day 1 = [6,5,4,3] (max=6), Day 2 = [2,1] (max=2). Total difficulty = 6 + 1 = 7.

Example 2 — Single Day

$ Input: jobDifficulty = [9,9,9], d = 1

› Output: 9

💡 Note: All jobs must be done in 1 day. The difficulty is the maximum job difficulty = 9.

Example 3 — Impossible Case

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

› Output: -1

💡 Note: Cannot schedule 3 jobs across 4 days since each day needs at least one job.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Jobs [6,5,4,3,2,1] must be scheduled across d=2 days

Process

Find partition that minimizes sum of daily maximums

Output

Optimal schedule gives minimum difficulty of 7

Key Takeaway

🎯 Key Insight: Use DP to efficiently try all valid partitions and minimize the sum of daily maximum difficulties

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to use dynamic programming to find the minimum sum of daily maximum difficulties. We can solve this with memoized recursion or bottom-up DP. Best approach is 2D DP with Time: O(n²×d), Space: O(n×d).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(d^n)	O(n)	Try all possible ways to partition jobs across d days using recursion
Memoization (Top-Down DP)	O(n² × d)	O(n × d)	Cache results of subproblems to avoid recalculating same states
Bottom-Up Dynamic Programming	O(n² × d)	O(n × d)	Build optimal solutions from smaller subproblems using a 2D DP table

Brute Force Recursion — Algorithm Steps

Try each possible ending position for current day
Recursively solve for remaining jobs and days
Return minimum difficulty found

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Day 1

Test different ending positions for first day

Recurse

Solve remaining jobs with remaining days

Minimum

Return the minimum difficulty found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solve(int* jobs, int n, int day, int start, int d) {
    if (day == d) {
        return start == n ? 0 : INT_MAX;
    }
    if (start >= n) return INT_MAX;
    
    int minDifficulty = INT_MAX;
    int maxJob = 0;
    
    for (int end = start; end < n - d + day + 1; end++) {
        if (jobs[end] > maxJob) maxJob = jobs[end];
        int remaining = solve(jobs, n, day + 1, end + 1, d);
        if (remaining != INT_MAX) {
            int current = maxJob + remaining;
            if (current < minDifficulty) {
                minDifficulty = current;
            }
        }
    }
    
    return minDifficulty;
}

int solution(int* jobDifficulty, int n, int d) {
    if (n < d) return -1;
    
    int result = solve(jobDifficulty, n, 1, 0, d);
    return result == INT_MAX ? -1 : result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int jobDifficulty[100];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        jobDifficulty[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int d;
    scanf("%d", &d);
    
    printf("%d\n", solution(jobDifficulty, n, d));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(d^n)

For each job, we try d different day assignments recursively

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth up to n levels

⚡ Linearithmic Space

85.0K Views

Medium Frequency

~35 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler