{x}
blog image

Minimum Difficulty of a Job Schedule

You want to schedule a list of jobs in d days. Jobs are dependent (i.e To work on the ith job, you have to finish all the 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.

You are given an integer array jobDifficulty and an integer d. The difficulty of the ith job is jobDifficulty[i].

Return the minimum difficulty of a job schedule. If you cannot find a schedule for the jobs return -1.

 

Example 1:

Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7

Example 2:

Input: jobDifficulty = [9,9,9], d = 4
Output: -1
Explanation: If you finish a job per day you will still have a free day. you cannot find a schedule for the given jobs.

Example 3:

Input: jobDifficulty = [1,1,1], d = 3
Output: 3
Explanation: The schedule is one job per day. total difficulty will be 3.

 

Constraints:

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

1335. Minimum Difficulty of a Job Schedule

Problem Description

You are given an array jobDifficulty representing the difficulty of each job and an integer d representing the number of days you have to schedule the jobs. Jobs must be completed in order. You must complete at least one job each day. The difficulty of a day is the maximum difficulty of any job completed that day. The total difficulty of a schedule is the sum of the daily difficulties. Find the minimum total difficulty of a valid schedule. If no valid schedule exists, return -1.

Solution: Dynamic Programming

This problem can be efficiently solved using dynamic programming.

State: dp[i][j] represents the minimum difficulty to schedule the first i jobs across j days.

Base Case: dp[0][0] = 0 (no jobs, no days). All other dp[i][0] and dp[0][j] are infinity (invalid).

Recurrence Relation: To calculate dp[i][j], we consider all possible ways to split the first i jobs into j days. Let's say we finish job k on day j. The minimum difficulty for this arrangement is:

dp[i][j] = min(dp[k-1][j-1] + max(jobDifficulty[k-1...i-1])) for k from 1 to i.

The max(jobDifficulty[k-1...i-1]) represents the maximum difficulty on day j, which is the maximum difficulty among jobs from k-1 to i-1.

Final Result: dp[n][d] (where n is the number of jobs) will hold the minimum difficulty if a solution exists; otherwise, it will remain at infinity.

Time and Space Complexity

  • Time Complexity: O(n²d), where n is the number of jobs and d is the number of days. This is due to the three nested loops in the dynamic programming solution.
  • Space Complexity: O(nd). This is due to the size of the dp table.

Code Implementation (Python)

def minDifficulty(jobDifficulty, d):
    n = len(jobDifficulty)
    if n < d:  # Not enough jobs for the given number of days
        return -1
 
    dp = [[float('inf')] * (d + 1) for _ in range(n + 1)]
    dp[0][0] = 0
 
    for i in range(1, n + 1):
        for j in range(1, min(i + 1, d + 1)):  # j <= i and j <= d
            max_difficulty = 0
            for k in range(i - 1, -1, -1): #Iterate backward to find max difficulty on the current day
                max_difficulty = max(max_difficulty, jobDifficulty[k])
                dp[i][j] = min(dp[i][j], dp[k][j - 1] + max_difficulty)
 
    return dp[n][d] if dp[n][d] != float('inf') else -1

The code iterates through all possible ways to assign jobs to days and stores the minimum difficulty for each subproblem in the dp table. It handles the case where no valid schedule exists by returning -1. Other languages (Java, C++, Go, TypeScript) will follow a very similar structure, just with syntax variations.