DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Minimum Amount of time to Brew Potion

Problem

/*
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;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)