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 <= 3000 <= jobDifficulty[i] <= 10001 <= d <= 10This approach uses a dynamic programming (DP) table to calculate the minimum difficulty schedule. The DP table is constructed such that dp[i][j] represents the minimum difficulty for scheduling the first i jobs in j days. We aim to fill this DP table using a bottom-up approach, iterating over all possible job and day combinations. For each combination, we calculate the scenario where the last day covers a range of jobs and obtains the minimum difficulty possible.
This implementation initializes a 2D DP table where dp[i][j] keeps track of the minimum difficulty for the first i jobs scheduled in j days. We iterate day by day and within each day, iterate over the possible jobs that can be scheduled. For each possible subarray, we calculate the maximum difficulty and adjust the DP table accordingly.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n2d), where n is the length of jobDifficulty and d is the number of days.
Space Complexity: O(nd), due to the storage of minimum difficulties in the DP table.
This approach is based on recursion with memoization. The main idea is to use a recursive function to find the minimum difficulty from a given starting index, splitting the jobs over the remaining days. For each recursive call, consider different partitions for the first day's job and compute the best possible schedule using range maximum queries and storing results to avoid redundant calculations.
This implementation utilizes a recursive depth-first search (DFS) function to handle the subproblem, memorizing results as each substate is calculated. The search accumulates the maximum difficulty for each possible partition of jobs for current day.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n2d), with memoization reducing redundant calculations.
Space Complexity: O(nd), storing calculated subproblems and recursion frames.
| Approach | Complexity |
|---|---|
| Dynamic Programming with Bottom-Up Approach | Time Complexity: O(n2d), where Space Complexity: O(nd), due to the storage of minimum difficulties in the DP table. |
| Recursive Approach with Memoization | Time Complexity: O(n2d), with memoization reducing redundant calculations. Space Complexity: O(nd), storing calculated subproblems and recursion frames. |
Minimum Difficulty of a Job Schedule | Recursion | Memoization | Amazon | Leetcode 1335 • codestorywithMIK • 50,743 views views
Watch 9 more video solutions →Practice Minimum Difficulty of a Job Schedule with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor