Welcome to Subscribe On Youtube

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

  • 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];
    }
}


  • 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];
    }
};


  • 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]


  • 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]
}


  • 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];
}

All Problems

All Solutions