2188. Minimum Time to Finish the Race
Problem Description
In this problem, you are provided with a tires array representing different types of tires a racing car can use. Each type of tire has a fatigue factor, meaning each successive lap takes longer to complete than the previous one. A tire's performance is defined by two parameters: f_i and r_i, where f_i is the time it takes to finish the first lap, and r_i is the factor by which the time increases for each subsequent lap.
Your goal is to finish a race consisting of numLaps as quickly as possible. You can start the race with any tire, and you can change tires between laps, which takes changeTime seconds. Changing to a new tire resets the fatigue for that tire, meaning it will perform its first lap at its f_i time again. Each tire type can be used an unlimited number of times.
The objective is to determine the minimum time required to complete the race.
Intuition
To solve this problem efficiently, one must combine dynamic programming with a greedy strategy to decide when to change tires.
Tire Performance Cost Calculation
First, we need to understand when it is beneficial to change a tire rather than keep using it. For each tire type, there is a point at which the increasing time due to fatigue makes it slower than just changing to a new tire. We calculate this break-even point under which it's better to keep using the tire and create a cost array representing the minimum time to finish a certain number of laps with a single tire before switching becomes faster.
Dynamic Programming
Next, we use dynamic programming to decide the minimum time to finish i laps. The state f[i] represents the minimum time to finish i laps. For each state, we consider using one of the optimal tire strategies for the last j laps (where j is derived from the previously calculated tire performance cost), and then find the minimum time taking f[i - j] + cost[j] + changeTime over all feasible j.
This dynamic programming algorithm will incrementally build up the answer until it gets to f[numLaps], which will be the final answer â the minimum time to finish the race.
Learn more about Dynamic Programming patterns.
Which data structure is used to implement priority queue?
Solution Approach
The solution involves both optimization through precalculating the best time for a certain number of laps with each tire and dynamic programming to decide on when to change the tires to result in the minimum total time.
Precalculating Tire Costs
We start by initializing a cost list to store the optimal tire usage time for each possible number of successive laps from 1 to a limit where changing tires is more efficient (in the given solution, the limit is 17 laps). We use infinity (inf) initially to signify that we have not calculated any times yet.
For each tire type given in the tires array, with f as the initial lap time and r as the fatigue factor, we iterate through successive laps, calculating the time it would take for that tire to complete up to that lap (applying r_i^(x-1) to the initial time f_i for each lap x). We update the cost list only if the time calculated (s) is less than what's already stored there, thereby keeping the minimum time for each possible number of successive laps.
This calculation is cut off at the point where the time for the next lap would exceed the time it would take to change tires and use a new one (changeTime + f).
Dynamic Programming Algorithm
Next, we define a dynamic programming array f to store the best time to finish i laps. We initialize the first element f[0] to -changeTime (since we do not need to account for a tire change at the start). We then iterate through the numLaps laps to be completed.
For each lap i, we consider every possible j number of laps that might have been completed with the current tire before changing (limited by the smaller of 17, representing our precalculated limit, and the current lap number i). We use these precalculated costs to determine if changing before the i-th lap is beneficial. The update is done using f[i] = min(f[i], f[i - j] + cost[j]), which represents the minimum time of completing i-j laps, then doing j laps on a new tire.
Finally, we add changeTime to f[i] as it represents the added time to change the tire after having completed i-j laps.
Conclusion
By iterating through all laps and all feasible js, the f array incrementally builds up the solutions until we reach f[numLaps], which gives us the minimum time to finish all numLaps. The implementation efficiently combines both the precalculation of an empirical threshold (based on tire performance) and a bottom-up dynamic programming approach to solve the problem.
Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?
Example Walkthrough
Let's consider a scenario where we have two tire types defined in the array tires as follows: [[2,3],[3,4]]. This means the first tire type has an initial lap time f1=2 seconds and a fatigue factor r1=3. The second tire has f2=3 seconds and r2=4. Let's also assume changeTime=10 seconds, and we want to complete numLaps=5 laps.
Precalculating Tire Costs
Before we start, we calculate the break-even points for each tire type using the provided intuition.
-
For tire type 1: Starting at 2 seconds, the lap times would be 2, 6 (2 * 3), 18 (6 * 3), ... We stop calculating when the next lap time is greater than
changeTime + f1= 12 seconds. So, we only consider the first two laps for this tire before changing. -
For tire type 2: Starting at 3 seconds, the times are 3, 12 (3 * 4), ... Again, we only consider the first lap for this tire because the second lap is already too slow.
From this precalculation, we determine that for our set of tires, using a tire for only the first lap before changing is the most efficient; this is what our cost list reflects.
Dynamic Programming Algorithm
Now we use dynamic programming to find the best strategy to complete all 5 laps. We initialize the array f with size numLaps+1 as f = [0, inf, inf, inf, inf, inf]. The first element represents the starting point with no laps completed.
-
To complete
1 lap (i=1), we check both tires for the first lap, which as per our precalculated costs, would take minimum of2and3seconds respectively. We do not have to change tires, so we pick the minimum time which is2seconds for tire type 1. Thusf[1] = 2. -
For
2 laps (i=2), since changing tires for each lap is most efficient, we look at the cost for1 lapand add a tire change time to that cost for each tire type. The minimum cost would be for tire type 1, which is2 seconds (previous lap) + 10 seconds (changeTime) + 2 seconds (new lap with tire type 1)=14 seconds. Thusf[2] = 14. -
Applying the same logic for
i=3, 4, and 5, we will find that changing tires every lap ensures the lowest possible time for each i-th lap. Therefore, forf[3]it would bef[2] + changeTime + cost[1], and sincecost[1]is2(using tire type 1),f[3]becomes26seconds; continuing this tillf[5], we getf[5] = 50seconds.
Conclusion
By combining precalculations of tire performance with dynamic programming, we have found that the minimum time to finish 5 laps using either of the two tire types, with the liberty to change tires after each lap, would be 50 seconds. The dynamic programming approach ensures that we consider every possible scenario at each stage (for each lap) and build upon previous computations to efficiently arrive at the final answer.
Solution Implementation
1from typing import List
2from math import inf
3
4class Solution:
5 def minimum_finish_time(self, tires: List[List[int]], change_time: int, num_laps: int) -> int:
6 # Initialize the minimum cost for each number of laps up to 17
7 # These values represent the minimum time to complete a given number of laps without changing tires
8 min_cost_for_laps = [inf] * 18
9
10 # Calculate the minimum time to complete successive laps with each tire configuration
11 for base_time, decay_factor in tires:
12 lap_count, current_cost, time_for_next_lap = 1, 0, base_time
13 # Continue if the time to complete the next lap is less than or equal to the time it takes to change the tire plus the base time
14 while time_for_next_lap <= change_time + base_time:
15 current_cost += time_for_next_lap
16 min_cost_for_laps[lap_count] = min(min_cost_for_laps[lap_count], current_cost)
17 # Increase the time for the next lap by the decay factor, and increment lap count
18 time_for_next_lap *= decay_factor
19 lap_count += 1
20
21 # Initialize the dp array to store the minimum time to finish a certain number of laps
22 min_time_to_finish_laps = [inf] * (num_laps + 1)
23 # Set the base case where 0 laps take 0 time, minus the time for tire change as it's not needed yet
24 min_time_to_finish_laps[0] = -change_time
25
26 # Calculate the minimum time to complete i laps
27 for lap_i in range(1, num_laps + 1):
28 # Consider all possible numbers of laps one could run before changing tires,
29 # but it is not worth considering more laps than the tire can handle before decaying, hence the min(18, lap_i + 1) limit
30 for consecutive_laps_with_one_tire in range(1, min(18, lap_i + 1)):
31 min_time_to_finish_laps[lap_i] = min(
32 min_time_to_finish_laps[lap_i],
33 min_time_to_finish_laps[lap_i - consecutive_laps_with_one_tire] + min_cost_for_laps[consecutive_laps_with_one_tire]
34 )
35 # Add the change time for each tire switch
36 min_time_to_finish_laps[lap_i] += change_time
37
38 # Return the minimum time to finish all the laps
39 return min_time_to_finish_laps[num_laps]
40
41# The rewritten code now has a clearer naming convention, follows Python 3 syntax,
42# and includes comments that explain what each part of the code does.
431import java.util.Arrays;
2
3class Solution {
4 public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {
5 // Initialize the infinity value to be used for the comparison.
6 final int infinity = 1 << 30;
7 // This array will store the minimum cost for laps up to 17, since for laps 18 and over
8 // it's better to change tires than to keep using the same tire.
9 int[] minCost = new int[18];
10 // Fill the cost array with infinity to later find the minimum.
11 Arrays.fill(minCost, infinity);
12
13 // Calculate the minimum cost for each tire for up to 17 laps.
14 for (int[] tire : tires) {
15 int firstLapTime = tire[0];
16 int rotFactor = tire[1];
17 int cumulativeTime = 0;
18 int lapTime = firstLapTime;
19
20 // Loop to calculate the time of using the same tire consecutively without changing.
21 for (int i = 1; lapTime <= changeTime + firstLapTime; ++i) {
22 cumulativeTime += lapTime;
23 minCost[i] = Math.min(minCost[i], cumulativeTime);
24 lapTime *= rotFactor; // Increase lap time by rotation factor for the next lap
25 }
26 }
27
28 // Initialize dp array to store the best time to complete i laps.
29 int[] f = new int[numLaps + 1];
30 // Fill the dp array with infinity.
31 Arrays.fill(f, infinity);
32 // Time to finish 0 lap is 0 minus the change time to account for the initial starting point (no tire change before the race).
33 f[0] = -changeTime;
34
35 // Compute the minimum time to finish each number of laps.
36 for (int i = 1; i <= numLaps; ++i) {
37 // Try every possible last stint that spans j laps (where j < 18 and j <= current lap number).
38 for (int j = 1; j < Math.min(18, i + 1); ++j) {
39 f[i] = Math.min(f[i], f[i - j] + minCost[j]);
40 }
41 // Add the tire change time since every stint ends with changing tires unless it's the final one.
42 f[i] += changeTime;
43 }
44
45 // Return the minimum time to finish all laps.
46 return f[numLaps];
47 }
48}
491class Solution {
2public:
3 int minimumFinishTime(vector<vector<int>>& tires, int changeTime, int numLaps) {
4 int minCost[18];
5 memset(minCost, 0x3f, sizeof(minCost)); // Initialize minCost to a large number
6
7 // Populate minCost array with the minimum cost of completing each number of laps (up to 17)
8 for (auto& tire : tires) {
9 int baseTime = tire[0]; // base lap time for this tire
10 int fatigueRate = tire[1]; // rate at which the tire gets slower each lap
11 int totalTime = 0; // total time to complete a certain number of laps with this tire
12 long long currentTime = baseTime; // time for the current lap
13 for (int laps = 1; currentTime <= changeTime + baseTime; ++laps) {
14 totalTime += currentTime;
15 minCost[laps] = min(minCost[laps], totalTime);
16 currentTime *= fatigueRate; // for the next lap, time increases by fatigueRate
17 }
18 }
19
20 int dp[numLaps + 1]; // dp[i] will store the minimum time to complete i laps
21 memset(dp, 0x3f, sizeof(dp)); // Initialize dp array to a large number
22 dp[0] = -changeTime; // base case: no time needed before starting
23
24 // Compute minimum time for each number of laps from 1 to numLaps
25 for (int i = 1; i <= numLaps; ++i) {
26 // Consider the time to do the last j laps
27 for (int j = 1; j < min(18, i + 1); ++j) {
28 dp[i] = min(dp[i], dp[i - j] + minCost[j] + changeTime);
29 }
30 }
31 // Return the minimum time to complete numLaps
32 return dp[numLaps];
33 }
34};
351function minimumFinishTime(tires: number[][], changeTime: number, numLaps: number): number {
2 // Define 'minCostPerLap' to store the minimum cost to complete each lap from 1 to 17 (inclusive).
3 // We use 18 because after certain laps, changing tires is cheaper than using worn out tires.
4 const minCostPerLap: number[] = Array(18).fill(Infinity);
5
6 // Calculate the minimum cost for each lap for all given tires configurations.
7 for (const [firstLapTime, lossFactor] of tires) {
8 let cumulativeTime = 0;
9 let currentTime = firstLapTime;
10
11 // Loop to calculate and update the minimum cost to complete 'i' laps without changing tires.
12 // This loop ends when the cost to run another lap is greater than the cost of changing tires plus the time of the first lap.
13 for (let i = 1; currentTime <= changeTime + firstLapTime; ++i) {
14 cumulativeTime += currentTime; // Add the current lap time to the cumulative time.
15 minCostPerLap[i] = Math.min(minCostPerLap[i], cumulativeTime); // Store the minimum cumulative time.
16 currentTime *= lossFactor; // Increment next lap time by the loss factor.
17 }
18 }
19
20 // Define 'totalCostToCompleteLaps' to store the total cost to complete from 0 to 'numLaps' laps.
21 const totalCostToCompleteLaps: number[] = Array(numLaps + 1).fill(Infinity);
22 totalCostToCompleteLaps[0] = -changeTime; // Initialize the 0th lap since there is no tire change needed initially.
23
24 // Calculate the total cost to complete 'i' laps.
25 for (let i = 1; i <= numLaps; ++i) {
26 // Evaluate the minimum cost for completing 'i' laps by either continuing with current tires or changing tires.
27 for (let j = 1; j < Math.min(18, i + 1); ++j) {
28 totalCostToCompleteLaps[i] = Math.min(
29 totalCostToCompleteLaps[i], // Current cost
30 totalCostToCompleteLaps[i - j] + minCostPerLap[j] // Cost of (i-j) laps + cost to complete 'j' laps without changing
31 );
32 }
33 // Add the time to change tires for going beyond the 0th lap.
34 totalCostToCompleteLaps[i] += changeTime;
35 }
36
37 // Return the total cost to complete 'numLaps' laps.
38 return totalCostToCompleteLaps[numLaps];
39}
40What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?
Time and Space Complexity
Time Complexity
The given code consists of two main parts: calculating the minimum cost to complete a lap using one set of tires for up to 17 consecutive laps and computing the minimum time to finish all numLaps.
-
Calculating minimum cost for each lap (up to 17):
- For each tire configuration, we iterate through laps, recalculating the time taken until it exceeds the change time plus the initial cost
f. - This while loop runs at most until
t <= changeTime + f, which depends on the rate of growth determined byr. The maximum number of iterations is limited to 17, as we stop adding laps costs once we reach this number (costarray size). - Since there are
Ttire configurations, the time complexity for this part becomes O(17T).
- For each tire configuration, we iterate through laps, recalculating the time taken until it exceeds the change time plus the initial cost
-
Computing minimum time to complete
numLaps:- We iterate over each lap from 1 to
numLapsinclusive. - For each lap, we iterate again for a maximum of 17 times (which is the maximum consecutive laps before a tire change is needed).
- At each inner loop iteration, we perform a constant number of operations seeking the minimum cost.
- The time complexity for this nested loop is O(numLaps * 17).
- We iterate over each lap from 1 to
Combining the two, we have the final time complexity:
O(17T) + O(numLaps * 17), simplifying this down to the major terms gives us O(T + numLaps).
Space Complexity
The space complexity of the given solution includes:
- The
costarray, which is of size 18 (constant size), giving O(1). - The
farray, which is of sizenumLaps + 1to store the minimum time to finish every possible number of laps.
Therefore, the overall space complexity is O(numLaps) because the size of f array scales with the input numLaps, which is the dominant term in space usage.
Learn more about how to find time and space complexity quickly using problem constraints.
A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".
What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.