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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Time to Finish the Race

Number: 2295

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given a set of tire types where each tire is represented as [f, r], the time needed to run the xth consecutive lap on that tire is f * r^(x-1). You have an unlimited supply of each tire. In a race of numLaps laps, you may start with any tire and after any lap you have the option to change tires by waiting changeTime seconds (even if you change to the same tire type). The goal is to find the minimum total time to finish all laps.

Key Insights

  • Precompute the optimal time to run a series of consecutive laps on a fresh tire without any tire change.
  • For each tire type, simulate consecutive laps until the lap time exceeds the cost of a tire change (since it would then be more beneficial to change tires).
  • Use dynamic programming (dp) where dp[i] represents the minimum time needed to finish i laps.
  • For each dp state, try using a segment of j consecutive laps (using the precomputed cost) and update dp[i] with dp[i - j] + cost[j] (adding changeTime if needed, except when finishing the race).
  • Optimize by limiting the maximum consecutive laps considered based on simulation results.

Space and Time Complexity

Time Complexity: O(numLaps * M) where M is the maximum number of consecutive laps simulated for a tire (typically small due to the exponential growth in lap time). Space Complexity: O(numLaps + M) for storing the dp array and the precomputed cost array.

Solution

We first precompute the minimum cost to run j consecutive laps on a new tire (without tire changes between laps). For each tire type [f, r], simulate lap by lap:

  1. For the 1st lap the cost is f.
  2. For each subsequent lap, multiply the previous lap’s time by r and add it to the cumulative time.
  3. Stop simulation for that tire if the cost for the next lap exceeds f + changeTime since it’s always better to change tires before such an expensive lap begins. During the simulation, update a global cost[j] with the minimum cumulative time among all tire types that can run j consecutive laps.

Then, use dynamic programming: let dp[i] be the minimum time to finish i laps. For each i from 1 to numLaps, try every possible segment length j (from 1 to min(i, max consecutive laps precomputed)) and update dp[i] using:   if i equals j (i.e. this segment covers the entire race), then:    dp[i] = min(dp[i], cost[j])   else:    dp[i] = min(dp[i], dp[i - j] + cost[j] + changeTime) This recurrence correctly adds the tire change penalty between segments except at the very start or when finishing the race.

Code Solutions

# Python solution with line-by-line comments

def minimumFinishTime(tires, changeTime, numLaps):
    # Precompute minimum cost for j consecutive laps on a new tire without changing
    # Initialize cost array with a large number for each lap count (index 0 unused)
    maxLaps_possible = numLaps  # we only need to compute up to numLaps laps
    cost = [float('inf')] * (maxLaps_possible + 1)
    
    # For each tire type, simulate consecutive laps until extra lap cost is too high.
    for f, r in tires:
        time = f  # time for the 1st lap with this tire
        total = 0
        lap = 1
        # Continue until current lap cost exceeds the cost of changing tire (break early)
        while time <= f + changeTime and lap <= maxLaps_possible:
            total += time
            # Update cost for current number of consecutive laps
            cost[lap] = min(cost[lap], total)
            time *= r  # time for next lap on the same tire
            lap += 1

    # Use dynamic programming where dp[i] = minimum time to finish i laps
    dp = [float('inf')] * (numLaps + 1)
    dp[0] = 0  # no time needed for 0 laps
    
    for lap in range(1, numLaps + 1):
        # Try using a segment of j consecutive laps ending at current lap count
        for j in range(1, min(lap, maxLaps_possible) + 1):
            # If this segment covers the whole race, no tire change cost is needed.
            if lap == j:
                dp[lap] = min(dp[lap], cost[j])
            else:
                dp[lap] = min(dp[lap], dp[lap - j] + cost[j] + changeTime)
    
    return dp[numLaps]

# Example usage:
if __name__ == "__main__":
    tires = [[2,3],[3,4]]
    changeTime = 5
    numLaps = 4
    print(minimumFinishTime(tires, changeTime, numLaps))  # Expected output: 21
← Back to All Questions