⚡Flashcard Drill➔
NeetCode #753LC-1335Hard2-D Dynamic Programming
← Back to All Problems

#753 · #1335 · Minimum Difficulty of a Job Schedule(工作计划的最低难度)

📌 Problem Statement & Constraints

You have jobDifficulty and d days. Split the jobs, in the given order, into exactly d non-empty consecutive groups. A day's difficulty is the maximum job in it, and the schedule's difficulty is the sum over days. Return the minimum schedule difficulty, or -1 if impossible. Constraints: 1 <= d <= jobDifficulty.length <= 300, 0 <= jobDifficulty[i] <= 1000.

💡 Core Algorithmic Approaches

  1. Let dp[day][i] be the minimum total difficulty for the first i jobs split into day days.
  2. A day is a contiguous block, so if the last day starts at index j, its difficulty is max(jobDifficulty[j:i]).
  3. Then dp[day][i] = min over j of (dp[day-1][j] + max(jobDifficulty[j:i])), with j ranging over valid starts for the last day.
  4. Extending the maximum backwards as j decreases makes the inner maximum O(1), so the total is O(n^2 * d).

💻 Benchmark Python3 Implementation

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)
        if n < d:
            return -1                   # every day needs at least one job
        INF = float("inf")
        dp = [INF] * (n + 1)
        dp[0] = 0
        for day in range(1, d + 1):
            nxt = [INF] * (n + 1)
            for i in range(day, n + 1):
                hardest = 0
                # j is the start index of the current (last) day
                for j in range(i - 1, day - 2, -1):
                    hardest = max(hardest, jobDifficulty[j])
                    if dp[j] < INF:
                        nxt[i] = min(nxt[i], dp[j] + hardest)
            dp = nxt
        return dp[n]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2 * d): each day's layer considers O(n^2) (start, end) pairs.
💾 Space Complexity
O(n): one rolling array.

⚠️ Interview Pitfalls & Follow-ups

  • Returning 0 when n < d: the schedule is impossible, so the answer is -1, not 0.
  • Using the sum instead of the max for a day: a day's difficulty is the maximum job in it, not the total.
  • Allowing an empty day: the inner loop's lower bound day - 1 guarantees each earlier day holds at least one job.
  • Recomputing max(jobDifficulty[j:i]) from scratch: extending the maximum backwards as j decreases gives it in O(1).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems