3494. Find the Minimum Amount of Time to Brew Potions

題目

You are given two integer arrays, skill and mana, of length n and m, respectively.

In a laboratory, n wizards must brew m potions in order. Each potion has a mana capacity mana[j] and must pass through all the wizards sequentially to be brewed properly. The time taken by the ith wizard on the jth potion is time_ij = skill[i] * mana[j].

Since the brewing process is delicate, a potion must be passed to the next wizard immediately after the current wizard completes their work. This means the timing must be synchronized so that each wizard begins working on a potion exactly when it arrives.

Return the minimum amount of time required for the potions to be brewed properly.

題目連結

題目的大意是會給定長度 n 的 skill 陣列代表 n 個巫師的工作效率(時間/魔量)，長度 m 的 potion 代表共有 m 瓶藥水要調製所需的魔量，例如：

skill = [1,5,2,4]

mana = [5,1,4,2]

代表有四個巫師要調至四罐藥水，且藥水調製的規則是每一罐藥水要依序經過每個巫師之手才算完成，而調製藥水所需的時間藥用巫師的工作效率乘上藥水的單位量也就是說第一罐藥水就會需要 5*(1+5+2+4)=60 的時間，依此類推。

此題的另一個重點是需要找到最小的總調製時間，因為藥水的調製可以時同時進行的，有點類似管線化的型態，也就是說當第二個巫師在調第一罐藥水時，第一個巫師可以同時進行第二罐藥水的形式，因此要在確保工作不會互相衝突的情況下找到所需時間的最小值。

思路

這題的關鍵在於需要觀察出第二輪之後的開始時間和前一輪的關聯性是什麼，需要遵守的一個原則是第 i 個巫師結束這一輪藥水的時間>=第 i+1 個巫師完成上一輪藥水的時間，因為這樣才能讓第 i+1 個巫師可以在做完上一輪之後可以銜接到這一輪。

參考上面的例子可以列出前兩輪的時間分配，第一輪從開始到最後一個巫師結束的時間是 [0, 5, 30, 40, 60]，假設第二輪的開始時間為 x，可以寫成 [x, x+1, x+6, x+8, x+12]。根據上面提到的原則，我們可以列出幾個關係式如下：

x >= 5
x+1 >= 30
x+6 >= 40
x+8 >= 60

把上述的條件彙整之後會得到 x>=52，所以在這邊取 x=52 就會是第二輪最小的開始時間，照著這樣的邏輯用一個二維矩陣來記錄，就可以把所有的時間分配表列出來，最後回傳最尾巴的那項即是題目所求的最短總時間。

Full Code

import numpy as np
from itertools import accumulate

class Solution:
    def minTime(self, skill: List[int], mana: List[int]) -> int:
        dp = np.zeros([len(mana), len(skill)])
        cumulative = np.array(list(accumulate(skill)))

        for idx, m in enumerate(mana):
            dp[idx] += m * cumulative
            if idx > 0:  
                time_diff = np.insert(dp[idx-1][0], 0, dp[idx-1][1:] - dp[idx][:-1])
                dp[idx] += max(time_diff)
        
        return int(dp[-1][-1])