LeetCode Entry

1335. Minimum Difficulty of a Job Schedule

29.12.2023 hard 2023 kotlin

Min sum of maximums jobDifficulty[i] per day d preserving the order

1335. Minimum Difficulty of a Job Schedule hard blog post substack youtube image.png

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(dn^2)\), dn for the recursion depth and another n for the inner loop

  • Space 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
  }