Find the Minimum Amount of Time to Brew Potions
You receive 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 i^th wizard on the j^th potion is timeij= 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.
Produce the minimum amount of time required for the potions to be brewed properly.
Input: skill = [1,5,2,4], mana = [5,1,4,2]
Output: 110
Explanation:
| Potion Number | Start time | Wizard 0 done by | Wizard 1 done by | Wizard 2 done by | Wizard 3 done by |
|---|---|---|---|---|---|
| 0 | 0 | 5 | 30 | 40 | 60 |
| 1 | 52 | 53 | 58 | 60 | 64 |
| 2 | 54 | 58 | 78 | 86 | 102 |
| 3 | 86 | 88 | 98 | 102 | 110 |
As an example for why wizard 0 cannot start working on the 1st potion before time t = 52 , consider the case where the wizards started preparing the 1st potion at time t = 50 . At time t = 58 , wizard 2 is done with the 1st potion, but wizard 3 will still be working on the 0th potion till time t = 60 .
Input: skill = [1,1,1], mana = [1,1,1]
Output: 5
Explanation:
-
Preparation of the 0^th potion begins at time
t = 0, and is completed by timet = 3. -
Preparation of the 1^st potion begins at time
t = 1, and is completed by timet = 4. -
Preparation of the 2^nd potion begins at time
t = 2, and is completed by timet = 5.
Input: skill = [1,2,3,4], mana = [1,2]
Output: 21
Constraints
n == skill.lengthm == mana.length1 <= n, m <= 50001 <= mana[i], skill[i] <= 5000
Did this problem appear in one of your interviews?
Responses stay private.