Page Contents
Minimum Difficulty of a Job Schedule Solution
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 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 in that day.
Given an array of integers jobDifficulty
and an integer d
. The difficulty of the i-th
job is jobDifficulty[i]
.
Also See: Amazon OA Online Assessment 2021 Questions and Answers
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.
Example 4:
Input: jobDifficulty = [7,1,7,1,7,1], d = 3 Output: 15
Example 5:
Input: jobDifficulty = [11,111,22,222,33,333,44,444], d = 6 Output: 843
Constraints:
1 <= jobDifficulty.length <= 300
0 <= jobDifficulty[i] <= 1000
1 <= d <= 10
Solution
Program C++
Consider dp[i][j] as the min difficulty for first i jobs in first j days. Since every day should be assinged atleast one job, ith job is done on jth day. By the same logic atleast first (j-1) jobs should be left for first (j-1) days. Now let us schedule jobs from k to i on the jth day, k varies from j to i.
class Solution { public: int minDifficulty(vector<int>& a, int d) { int n=a.size(); if(n<d) return -1; int dp[n+1][d+1]; fill_n(&dp[0][0],(n+1)*(d+1),1e9); dp[0][0]=0; for(int i=1;i<=n;i++){ for(int j=1;j<=d;j++){ int mx=0; for(int k=i;k>=j;k--){ mx=max(mx,a[k-1]); if(dp[k-1][j-1]<1e9) dp[i][j]=min(dp[i][j],mx+dp[k-1][j-1]); } } } return dp[n][d]; } };
Program Java
class Solution { public int minDiff(int[] jobs, int start, int n, int d, int[][] dp){ if (n > d) return 0; //if calculated before if (dp[start][n] != -1) return dp[start][n]; //int the last step, we need to take the maximum of the rest of elements if (n == d){ int currentMax = Integer.MIN_VALUE; for (int i=start;i<jobs.length;i++){ currentMax = Math.max(currentMax, jobs[i]); } dp[start][n] = currentMax; return currentMax; } int min = Integer.MAX_VALUE; int currentMax = Integer.MIN_VALUE; //loop until before jobs.length-(d-n) to make sure we have enough jobs for the rest of the days for (int i=start;i<jobs.length-(d-n);i++){ currentMax = Math.max(currentMax, jobs[i]); min = Math.min(min, minDiff(jobs, i+1, n+1, d, dp)+currentMax); } dp[start][n] = min; return min; } public int minDifficulty(int[] jobDifficulty, int d) { //if days is more than the jobs, then we can't proceed if (d > jobDifficulty.length) return -1; //init our dynamic programming array int[][] dp = new int[jobDifficulty.length][d+1]; for (int i=0;i<dp.length;i++){ for (int j=0;j<dp[0].length;j++) dp[i][j] = -1; } return minDiff(jobDifficulty,0, 1, d, dp); } }
Program Python
""" dp[i][k] := minimum difficulty of a k days job schedule, D[:i]. maxInRange[i][j] := max(D[i:j+1]) """ class Solution(object): def minDifficulty(self, D, K): if not D or not K or K>len(D): return -1 N = len(D) maxInRange = [[0 for _ in xrange(N)] for _ in xrange(N)] for i in xrange(N): maxInRange[i][i] = D[i] for l in xrange(2, N+1): for i in xrange(N): j = i+l-1 if j>=N: continue maxInRange[i][j] = max(maxInRange[i+1][j-1], D[i], D[j]) dp = [[float('inf') for _ in xrange(K+1)] for _ in xrange(N+1)] dp[0][0] = 0 for i in xrange(1, N+1): for k in xrange(1, min(i, K)+1): for j in xrange(k, i+1): dp[i][k] = min(dp[i][k], dp[j-1][k-1]+maxInRange[j-1][i-1]) #if you don't pre-calculate maxInRange #dp[i][k] = min(dp[i][k], dp[j-1][k-1]+max(D[j-1:i])) return dp[N][K]
Also See: AMCAT Study Materials, Preparation Guide
Also See: Microsoft Online Assessment Questions and Solution
Amazon Online Assessment Questions:
- Robot Bounded in Box
- Number Game
- Find All Combination of Numbers Sum to Target / Shopping Options
- Fill the Truck
- Music Pairs
- Slowest key
- Five Star Seller
- Split String Into Unique Primes
- Storage Optimization
- Minimum Difficulty of a Job Schedule
- Autoscale Policy, Utilization Check
- Optimal Utilization
- Merge Two Sorted Lists
- Two Sum Unique Pairs
- Shopping Patterns
- Reorder Data in Log Files
- Top K Frequent Words
- Trees Height
- Counting Binary Substrings Amazon OA Solution
- Grid Connections Amazon OA Solution
- Shipment Imbalance Amazon OA Solution
- Max Profit Amazon OA Solution
- Find Lowest Price Amazon OA Solution
- Simple Cipher Amazon OA Solution
- Decode String Frequency Amazon OA Solution
- Valid Discount Coupons Amazon OA Solution
- Count Maximum Teams Amazon OA Solution
- Minimum Coin Flips Amazon OA Solution