We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Minimum Amount of Time to Brew Potions

Difficulty: Medium

Problem 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 time_ij = 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.

Key Insights

  • Each wizard processes every potion sequentially, and the next potion can only be started after the current one is completed by all wizards.
  • The time taken by each wizard to brew a potion is dependent on both their skill level and the mana required for that potion.
  • We need to keep track of the completion time of each potion and ensure that each wizard starts their next potion only after they finish the previous one.

Space and Time Complexity

Time Complexity: O(n * m)
Space Complexity: O(1)

Solution

To solve the problem, we can use a simulation approach. We'll maintain a time variable for each wizard to track when they will finish the current potion. We will iterate over each potion and calculate when each wizard finishes their work based on their skill and the mana required for the potion. We update the start time of the next potion based on when the last wizard finishes the current potion.

  1. Initialize an array to keep track of the end times for each wizard.
  2. For each potion, calculate the time taken for each wizard in sequence:
    • For each wizard, compute their finish time based on their skill and the mana of the current potion.
    • Update the finish time of the wizard based on when they can start working (either immediately after they finish the last potion or when the previous wizard finishes).
  3. Return the finish time of the last wizard after all potions have been processed.

Code Solutions

def minTimeToBrewPotions(skill, mana):
    n = len(skill)
    m = len(mana)
    end_time = [0] * n  # Initialize the end times for each wizard

    for j in range(m):  # For each potion
        for i in range(n):  # For each wizard
            # Calculate when the wizard i can start working on potion j
            start_time = max(end_time[i], end_time[i - 1] if i > 0 else 0)
            end_time[i] = start_time + skill[i] * mana[j]  # Update the end time

    return end_time[-1]  # The time when the last wizard finishes the last potion
← Back to All Questions