1335. Minimum Difficulty of a Job Schedule LeetCode Solution

Last updated: February 23, 2025

In this guide, you will get 1335. Minimum Difficulty of a Job Schedule LeetCode Solution with the best time and space complexity. The solution to Minimum Difficulty of a Job Schedule problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Difficulty of a Job Schedule solution in C++
Minimum Difficulty of a Job Schedule solution in Java
Minimum Difficulty of a Job Schedule solution in Python
Additional Resources

1335. Minimum Difficulty of a Job Schedule LeetCode Solution image

Problem Statement of 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

Complexity Analysis

Time Complexity: O(n^2d)
Space Complexity: O(nd)

1335. Minimum Difficulty of a Job Schedule LeetCode Solution in C++

class Solution {
 public:
  int minDifficulty(vector<int>& jobDifficulty, int d) {
    const int n = jobDifficulty.size();
    if (n < d)
      return -1;

    // dp[i][k] := the minimum difficulty to schedule the first i jobs in k days
    vector<vector<int>> dp(n + 1, vector<int>(d + 1, INT_MAX / 2));
    dp[0][0] = 0;

    for (int i = 1; i <= n; ++i)
      for (int k = 1; k <= d; ++k) {
        int maxDifficulty = 0;                  // max(job[j + 1..i])
        for (int j = i - 1; j >= k - 1; --j) {  // 1-based
          maxDifficulty = max(maxDifficulty, jobDifficulty[j]);  // 0-based
          dp[i][k] = min(dp[i][k], dp[j][k - 1] + maxDifficulty);
        }
      }

    return dp[n][d];
  }
};
/* code provided by PROGIEZ */

1335. Minimum Difficulty of a Job Schedule LeetCode Solution in Java

class Solution {
  public int minDifficulty(int[] jobDifficulty, int d) {
    final int n = jobDifficulty.length;
    if (n < d)
      return -1;

    // dp[i][k] := the minimum difficulty to schedule the first i jobs in k days
    int[][] dp = new int[n + 1][d + 1];
    Arrays.stream(dp).forEach(A -> Arrays.fill(A, Integer.MAX_VALUE / 2));
    dp[0][0] = 0;

    for (int i = 1; i <= n; ++i)
      for (int k = 1; k <= d; ++k) {
        // max(job[j + 1..i])
        int maxDifficulty = 0;
        for (int j = i - 1; j >= k - 1; --j) {                       // 1-based
          maxDifficulty = Math.max(maxDifficulty, jobDifficulty[j]); // 0-based
          dp[i][k] = Math.min(dp[i][k], dp[j][k - 1] + maxDifficulty);
        }
      }

    return dp[n][d];
  }
}
// code provided by PROGIEZ

1335. Minimum Difficulty of a Job Schedule LeetCode Solution in Python

class Solution:
  def minDifficulty(self, jobDifficulty: list[int], d: int) -> int:
    n = len(jobDifficulty)
    if d > n:
      return -1

    # dp[i][k] := the minimum difficulty to schedule the first i jobs in k days
    dp = [[math.inf] * (d + 1) for _ in range(n + 1)]
    dp[0][0] = 0

    for i in range(1, n + 1):
      for k in range(1, d + 1):
        maxDifficulty = 0  # max(job[j + 1..i])
        for j in range(i - 1, k - 2, -1):  # 1-based
          maxDifficulty = max(maxDifficulty, jobDifficulty[j])  # 0-based
          dp[i][k] = min(dp[i][k], dp[j][k - 1] + maxDifficulty)

    return dp[n][d]
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents