Minimum Difficulty of a Job Schedule

Intuition

We define a state dp[i][j] where i is the days we have used and j is the number of finished jobs, and dp[i][j] is the minimum difficulty we need to schedule this jobs.

dp[i][j] = max([dp[i - 1][k] + max(difficulty[k:j]) for k in [0, j])

And we could add a optimize here which is to calculate the max(difficulty[k:j]) before the dp process. And the overall time complexity would be

O(d * jobs * jobs + jobs * jobs)

Solution


class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        jobs = len(jobDifficulty)

        # max_diff[i][j] is max(jobDifficulty[i:j + 1])
        max_diff = [[0] * jobs for _ in range(jobs)]
        for start in range(jobs):
            m = jobDifficulty[start]
            for last in range(start, jobs):
                m = max(m, jobDifficulty[last])
                max_diff[start][last] = m

        dp = [[float('inf')] * jobs for _ in range(d)]
        # Initial states for DP
        for finished in range(jobs):
            dp[0][finished] = max_diff[0][finished]

        # DP process
        for day in range(1, d):
            for lastday_finished in range(day - 1, jobs):
                for finished in range(lastday_finished + 1, jobs):
                    new_diff = max_diff[lastday_finished + 1][finished]
                    dp[day][finished] = min(
                        dp[day][finished],
                        dp[day - 1][lastday_finished] + new_diff
                        )

        result = dp[d - 1][jobs - 1]
        return -1 if result == float('inf') else result