Skip to content

3494. Find the Minimum Amount of Time to Brew Potions

Description

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.

 

Example 1:

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.

Example 2:

Input: skill = [1,1,1], mana = [1,1,1]

Output: 5

Explanation:

  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.

Example 3:

Input: skill = [1,2,3,4], mana = [1,2]

Output: 21

 

Constraints:

  • n == skill.length
  • m == mana.length
  • 1 <= n, m <= 5000
  • 1 <= mana[i], skill[i] <= 5000

Solutions

Solution 1: Dynamic Programming

We define \(f[i]\) as the time when wizard \(i\) completes the previous potion.

For the current potion \(x\), we need to calculate the completion time for each wizard. Let \(\textit{tot}\) represent the completion time of the current potion, initially \(\textit{tot} = 0\).

For each wizard \(i\), the time he starts processing the current potion is \(\max(\textit{tot}, f[i])\), and the time required to process this potion is \(skill[i] \times mana[x]\). Therefore, the time he completes this potion is \(\max(\textit{tot}, f[i]) + skill[i] \times mana[x]\). We update \(\textit{tot}\) to this value.

Since the brewing process requires that the potion must be immediately passed to the next wizard and processing must start immediately after the current wizard completes their work, we need to update the completion time \(f[i]\) for each wizard's previous potion. For the last wizard \(n-1\), we directly update \(f[n-1]\) to \(\textit{tot}\). For other wizards \(i\), we can update \(f[i]\) by traversing in reverse order, specifically, \(f[i] = f[i+1] - skill[i+1] \times mana[x]\).

Finally, \(f[n-1]\) is the minimum total time required to complete brewing all potions.

The time complexity is \(O(n \times m)\) and the space complexity is \(O(n)\), where \(n\) and \(m\) are the number of wizards and potions respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def minTime(self, skill: List[int], mana: List[int]) -> int:
        max = lambda a, b: a if a > b else b
        n = len(skill)
        f = [0] * n
        for x in mana:
            tot = 0
            for i in range(n):
                tot = max(tot, f[i]) + skill[i] * x
            f[-1] = tot
            for i in range(n - 2, -1, -1):
                f[i] = f[i + 1] - skill[i + 1] * x
        return f[-1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public long minTime(int[] skill, int[] mana) {
        int n = skill.length;
        long[] f = new long[n];
        for (int x : mana) {
            long tot = 0;
            for (int i = 0; i < n; ++i) {
                tot = Math.max(tot, f[i]) + skill[i] * x;
            }
            f[n - 1] = tot;
            for (int i = n - 2; i >= 0; --i) {
                f[i] = f[i + 1] - skill[i + 1] * x;
            }
        }
        return f[n - 1];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    long long minTime(vector<int>& skill, vector<int>& mana) {
        int n = skill.size();
        vector<long long> f(n);
        for (int x : mana) {
            long long tot = 0;
            for (int i = 0; i < n; ++i) {
                tot = max(tot, f[i]) + 1LL * skill[i] * x;
            }
            f[n - 1] = tot;
            for (int i = n - 2; i >= 0; --i) {
                f[i] = f[i + 1] - 1LL * skill[i + 1] * x;
            }
        }
        return f[n - 1];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func minTime(skill []int, mana []int) int64 {
    n := len(skill)
    f := make([]int64, n)
    for _, x := range mana {
        var tot int64
        for i := 0; i < n; i++ {
            tot = max(tot, f[i]) + int64(skill[i])*int64(x)
        }
        f[n-1] = tot
        for i := n - 2; i >= 0; i-- {
            f[i] = f[i+1] - int64(skill[i+1])*int64(x)
        }
    }
    return f[n-1]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function minTime(skill: number[], mana: number[]): number {
    const n = skill.length;
    const f: number[] = Array(n).fill(0);
    for (const x of mana) {
        let tot = 0;
        for (let i = 0; i < n; ++i) {
            tot = Math.max(tot, f[i]) + skill[i] * x;
        }
        f[n - 1] = tot;
        for (let i = n - 2; i >= 0; --i) {
            f[i] = f[i + 1] - skill[i + 1] * x;
        }
    }
    return f[n - 1];
}

Comments