Minimum Difficulty of a Job Schedule Amazon OA 2023

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].

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

Minimum Difficulty of a Job Schedule Amazon OA 2023

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
Minimum Difficulty of a Job Schedule Amazon
Minimum Difficulty of a Job Schedule Amazon

SOLUTION

Program: Minimum Difficulty of a Job Schedule Solution in 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: Minimum Difficulty of a Job Schedule Solution in 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: Minimum Difficulty of a Job Schedule Solution in 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]

Amazon OA 2023 Questions with Solution

  1. Shopping Patterns Solution Amazon OA 2023
  2. Reorder Data in Log Files Solution Amazon OA 2023
  3. Top K Frequent Words Solution Amazon OA 2023
  4. Trees Height Solution Amazon OA SDE 2023
  5. Counting Binary Substrings Amazon OA 2023
  6. Grid Connections Amazon OA 2023
  7. Shipment Imbalance Amazon OA 2023
  8. Max Profit Amazon OA 2023
  9. Find Lowest Price Amazon OA 2023
  10. Decode String Frequency Amazon OA 2023
  11. Simple Cipher Amazon OA 2023
  12. Valid Discount Coupons Amazon OA 2023 Solution
  13. Count Maximum Teams Amazon OA 2023
  14. Minimum Coin Flips Amazon OA 2023
  15. Max Average Stock Price Amazon OA 2023 Solution
  16. Robot Bounded In Circle Amazon OA 2023
  17. Shopping Options Amazon OA 2023 Solution
  18. Fill The Truck Maximum Units on a Truck Amazon OA Solution
  19. Maximize Score After N Operations Number Game Solution Amazon OA 2023
  20. Slowest Key Amazon OA 2023 Solution
  21. Five Star Seller Maximum Average Pass Ratio Amazon OA 2023
  22. Split String Into Unique Primes Amazon OA 2023 Solution
  23. Storage Optimization Amazon OA 2023 Solution
  24. Autoscale Policy Utilization Check Amazon OA 2023
  25. Optimal Utilization Solution Amazon OA 2023
  26. Merge Two Sorted Lists Solution Amazon OA 2023
  27. Two Sum Unique Pairs Solution Amazon OA 2023
  28. Amazon Music Pairs Amazon OA 2023 Solution
  29. Class Grouping Amazon OA 2023 Solution
  30. Find Max products Amazon OA 2023 Solution
  31. Get encrypted number Amazon OA 2023 Solution
  32. Find Total Imbalance Amazon OA 2023 Solution
  33. Find Total Power Amazon OA 2023 Solution