/*
Let start[j] denote the time at which potion j starts at wizard 0.
Because each potion passes through every wizard sequentially, the time potion j reaches wizard i is:
start[j] + mana[j]* summation(k=0 to i-1) of skill[k]
Now consider two consecutive potions, j-1 and j.
For every wizard i, potion j must not reach that wizard before the wizard has finished processing potion j-1.
This gives us a constraint on start[j].Your task is to derive the constraint.
The finishing time of potion j-1 at wizard i is:
start[j-1] + mana[j-1] * summation(k =0 to i) of skill[k]
The arrival time of potion j at wizard i is:
start[j] + mana[j] * summation(k =0 to i-1) of skill[k]
Since the wizard must be available when the next potion arrives, we need:
Arrival time of j >= finish time of j-1
i.e
start[j] + mana[j] * summation(k =0 to i-1) of skill[k] >= start[j-1] + mana[j-1] * summation(k =0 to i) of skill[k]
Rearrange this inequality to get a lower bound for start[j].
For every wizard i, the lower bound (atleast start time for potion j) i.e start[j] is:
start[j-1] + mana[j-1]*summation(k = 0 to i) of skill[k] - mana[j]*summation(k=0 to i-1) skill[k]
Two important details:
1. For the previous potion, sum skills from 0 through i, inclusive, because wizard i must finish that potion.
2. For the current potion, sum skills from 0 through i-1, because the potion must arrive at wizard i before it starts processing.
Since this condition must hold for every wizard, we take the maximum lower bound across all wizards:
start[j] = Math.max(lowerboundStart[j] for all the wizards i to m-1)
*/
class Solution {
public long minTime(int[] skill, int[] mana) {
int m = skill.length;
int n = mana.length;
long prefix[] = new long[m];
long sum =0;
for(int i = 0;i<m;i++){
sum+=skill[i];
prefix[i] = sum;
}
long prevStartTime = 0;
long prevFinish = prevStartTime + mana[0]*prefix[m-1];
for(int j = 1;j<n;j++){
long maxLowestStartTime = Long.MIN_VALUE;
for(int i = 0;i<m;i++){
maxLowestStartTime = Math.max(maxLowestStartTime, prevStartTime + mana[j-1]*prefix[i] - ((i-1) < 0 ? 0 : mana[j]*prefix[i-1]));
}
prevFinish = maxLowestStartTime + mana[j]*prefix[m-1];
prevStartTime = maxLowestStartTime;
}
return prevFinish;
}
}
For further actions, you may consider blocking this person and/or reporting abuse
Top comments (0)