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 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.
Return 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: 5Explanation:
1. Preparation of the 0th potion begins at time `t = 0`, and is completed by time `t = 3`.2. Preparation of the 1st potion begins at time `t = 1`, and is completed by time `t = 4`.3. Preparation of the 2nd potion begins at time `t = 2`, and is completed by time `t = 5`.
Potions must be brewed “in order” while each individual potion flows continuously through all wizards without ever waiting between wizards. Different potions may overlap (pipeline effect) but you may not allow a potion to sit idle waiting for a busy downstream wizard. That condition means: when potion j arrives at wizard i, that wizard must already be free (i.e., finished potion j-1). Therefore we must pick a start time S_j for each potion so that every handoff along its path is wait‑free.
Let pref[i] = skill[0] + ... + skill[i]. Processing time of potion j on wizard i is skill[i] * mana[j]. If potion j starts at S_j, the time it reaches wizard i (start at wizard i) is:
Taking the maximum over all i gives the tightest feasible start time:
S_j = S_{j-1} + max_{0 <= i < n} ( pref[i] * mana[j-1] - pref[i-1] * mana[j] ) with pref[-1]=0.
Base: S_0 = 0. Total completion time after last potion m-1 is:
Answer = S_{m-1} + pref[n-1] * mana[m-1].
Edge cases: if m = 1, answer is simply pref[n-1] * mana[0].
This matches the sample (see derived deltas in commentary) and fixes earlier incorrect formulations that allowed mid-potion waiting or mis-initialized the delta by using skill[0] * mana[j] instead of the correct pref[0] * mana[j-1] term.
classSolution {
publiclongminTime(int[] skill, int[] mana) {
int n = skill.length, m = mana.length;
long[] pref =newlong[n];
pref[0]= skill[0];
for (int i = 1; i < n; ++i) pref[i]= pref[i-1]+ skill[i];
if (m == 1) return pref[n-1]* mana[0];
long S = 0L; // start time of current potionfor (int j = 1; j < m; ++j) {
long delta = pref[0]* (long) mana[j-1]; // i=0 term (pref[-1]=0)for (int i = 1; i < n; ++i) {
long cand = pref[i]* (long) mana[j-1]- pref[i-1]* (long) mana[j];
if (cand > delta) delta = cand;
}
S += delta;
}
return S + pref[n-1]* (long) mana[m-1];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
classSolution {
funminTime(skill: IntArray, mana: IntArray): Long {
val n = skill.size; val m = mana.size
val pref = LongArray(n)
pref[0] = skill[0].toLong()
for (i in1 until n) pref[i] = pref[i-1] + skill[i]
if (m ==1) return pref[n-1] * mana[0]
var S = 0Lfor (j in1 until m) {
var delta = pref[0] * mana[j-1]
for (i in1 until n) {
val cand = pref[i] * mana[j-1] - pref[i-1] * mana[j]
if (cand > delta) delta = cand
}
S += delta
}
return S + pref[n-1] * mana[m-1]
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classSolution:
defminTime(self, skill: list[int], mana: list[int]) -> int:
n, m = len(skill), len(mana)
pref = [0]*n
pref[0] = skill[0]
for i in range(1, n):
pref[i] = pref[i-1] + skill[i]
if m ==1:
return pref[-1] * mana[0]
S =0for j in range(1, m):
delta = pref[0] * mana[j-1] # i=0 termfor i in range(1, n):
cand = pref[i] * mana[j-1] - pref[i-1] * mana[j]
if cand > delta:
delta = cand
S += delta
return S + pref[-1] * mana[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
impl Solution {
pubfnmin_time(skill: Vec<i32>, mana: Vec<i32>) -> i64 {
let n = skill.len(); let m = mana.len();
letmut pref =vec![0i64; n];
pref[0] = skill[0] asi64;
for i in1..n { pref[i] = pref[i-1] + skill[i] asi64; }
if m ==1 { return pref[n-1] * mana[0] asi64; }
letmut s: i64=0;
for j in1..m {
letmut delta = pref[0] * mana[j-1] asi64;
for i in1..n {
let cand = pref[i] * mana[j-1] asi64- pref[i-1] * mana[j] asi64;
if cand > delta { delta = cand; }
}
s += delta;
}
s + pref[n-1] * mana[m-1] asi64 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
classSolution {
minTime(skill: number[], mana: number[]):number {
constn=skill.length, m=mana.length;
constpref: number[] =new Array(n);
pref[0] =skill[0];
for (leti=1; i<n; ++i) pref[i] =pref[i-1] +skill[i];
if (m===1) returnpref[n-1] *mana[0];
letS=0; // start time accumulator
for (letj=1; j<m; ++j) {
letdelta=pref[0] *mana[j-1];
for (leti=1; i<n; ++i) {
constcand=pref[i] *mana[j-1] -pref[i-1] *mana[j];
if (cand>delta) delta=cand;
}
S+=delta;
}
returnS+pref[n-1] *mana[m-1];
}
}