We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Difficulty of a Job Schedule

Number: 1457

Difficulty: Hard

Paid? No

Companies: TikTok, Salesforce, Amazon, Adobe, Turvo

Problem Description

Given a list of jobs with their associated difficulties and a fixed number of days, partition the jobs (maintaining their given order) so that each day you complete at least one job. The difficulty of each day is defined as the maximum difficulty of the jobs performed that day. The goal is to minimize the total difficulty which is the sum across all days. If it is not possible to schedule the jobs in d days, return -1.

Key Insights

  • Use dynamic programming to break the problem into subproblems by scheduling the first i jobs over a specific number of days.
  • Define a DP state dp[i][day] representing the minimum total difficulty for scheduling the first i jobs in "day" days.
  • Transition by iterating backwards to form the current day’s block, updating the maximum difficulty as you include more jobs.
  • The answer is dp[n][d], where n is the total number of jobs.
  • Edge case: if the number of jobs is less than d, it's impossible to schedule, return -1.

Space and Time Complexity

Time Complexity: O(n^2 * d) – Iterating over days and for each, iterating over all possible partitions. Space Complexity: O(n * d) – For maintaining the DP table.

Solution

We utilize a 2D DP array to store our intermediate results. For every day (from 1 to d) and every job index, we update the DP table by considering all valid partitions where the current day receives a block of consecutive jobs. As we backtrack, we maintain the maximum difficulty encountered for the current day, and combine it with the previous optimal schedule stored in the DP table. This ensures that each partition minimizes the total difficulty across all days.

Code Solutions

def minDifficulty(jobDifficulty, d):
    n = len(jobDifficulty)
    # If there are fewer jobs than days, it's not possible to schedule
    if n < d:
        return -1

    # DP table: dp[i][day] represents the minimum difficulty for the first i jobs in "day" days.
    dp = [[float('inf')] * (d + 1) for _ in range(n + 1)]
    dp[0][0] = 0

    # For each day, decide the partition of jobs.
    for day in range(1, d + 1):
        # i loops from "day" because at least one job must be done per day.
        for i in range(day, n + 1):
            max_difficulty = 0
            # Evaluate possible partitions by going backward.
            for j in range(i - 1, day - 2, -1):
                max_difficulty = max(max_difficulty, jobDifficulty[j])
                dp[i][day] = min(dp[i][day], dp[j][day - 1] + max_difficulty)
    
    return dp[n][d]

# Example usage:
print(minDifficulty([6,5,4,3,2,1], 2))  # Expected output: 7
← Back to All Questions