# 29.12.2023 [1335. Minimum Difficulty of a Job Schedule]
Min sum of maximums jobDifficulty[i] per day d preserving the order
29.12.2023
1335. Minimum Difficulty of a Job Schedule hard
blog post
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/454
Problem TLDR
Min sum of maximums jobDifficulty[i] per day d preserving the order
Intuition
Let’s brute-force optimal interval of jobs jobInd..j
for every day using Depth-First Search. The result will only depend on the starting jobInd
and the current day
, so can be cached.
Approach
pay attention to the problem description, preserving jobs order matters here
Complexity
Time complexity:
O(dn2),dn
for the recursion depth and anothern
for the inner loopSpace complexity:
O(dn)
Code
fun minDifficulty(jobDifficulty: IntArray, d: Int): Int {
val dp = mutableMapOf<Pair<Int, Int>, Int>()
fun dfs(jobInd: Int, day: Int): Int = when {
jobInd == jobDifficulty.size -> if (day == d) 0 else Int.MAX_VALUE / 2
day == d -> Int.MAX_VALUE / 2
else -> dp.getOrPut(jobInd to day) {
var max = 0
(jobInd..jobDifficulty.lastIndex).minOf { i ->
max = max(max, jobDifficulty[i])
max + dfs(i + 1, day + 1)
}
}}
return dfs(0, 0).takeIf { it < Int.MAX_VALUE / 2 } ?: -1
}