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

Minimum Time to Finish the Race

Difficulty: Hard

Problem Description

You are given a 0-indexed 2D integer array tires where tires[i] = [fi, ri] indicates that the i-th tire can finish its x-th successive lap in fi * ri^(x-1) seconds. You are also given an integer changeTime and an integer numLaps. The race consists of numLaps laps, and you may start the race with any tire. You have an unlimited supply of each tire and after every lap, you may change to any given tire (including the current tire type) if you wait changeTime seconds. Return the minimum time to finish the race.

Key Insights

  • The time to complete each lap increases exponentially based on the number of consecutive laps using the same tire.
  • Changing tires incurs a fixed time penalty (changeTime).
  • We aim to balance the cost of changing tires with the cumulative lap times to minimize the overall time.
  • We can efficiently calculate the minimum time required for a certain number of laps using dynamic programming.

Space and Time Complexity

Time Complexity: O(numLaps * log(numLaps))
Space Complexity: O(numLaps)

Solution

To solve the problem, we can use dynamic programming:

  1. For each tire, calculate the time for a varying number of consecutive laps until the time exceeds the changeTime.
  2. Maintain a minimum time array where each index represents the minimum time to complete that number of laps.
  3. Update the minimum time for each lap by considering both the option to continue with the current tire and the option to change tires.
  4. The result is found in the minimum time array after processing all laps.

Code Solutions

def minimumFinishTime(tires, changeTime, numLaps):
    # Initialize an array to store the minimum time for each lap
    min_time = [float('inf')] * (numLaps + 1)
    min_time[0] = 0  # Base case: 0 laps cost 0 time

    # Calculate the minimum time for each tire
    for f, r in tires:
        lap_time = f
        total_time = f
        lap_count = 1
        
        # Calculate the time for the first few laps using the tire
        while lap_count <= numLaps and lap_time <= changeTime:
            min_time[lap_count] = min(min_time[lap_count], total_time)
            lap_count += 1
            lap_time *= r
            total_time += lap_time

    # Dynamic programming to calculate the minimum time for numLaps
    for i in range(1, numLaps + 1):
        for j in range(1, i + 1):
            min_time[i] = min(min_time[i], min_time[i - j] + changeTime + min_time[j])

    return min_time[numLaps]
← Back to All Questions