{x}
blog image

Minimum Time to Finish the Race

You are given a 0-indexed 2D integer array tires where tires[i] = [fi, ri] indicates that the ith tire can finish its xth successive lap in fi * ri(x-1) seconds.

  • For example, if fi = 3 and ri = 2, then the tire would finish its 1st lap in 3 seconds, its 2nd lap in 3 * 2 = 6 seconds, its 3rd lap in 3 * 22 = 12 seconds, etc.

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.

 

Example 1:

Input: tires = [[2,3],[3,4]], changeTime = 5, numLaps = 4
Output: 21
Explanation: 
Lap 1: Start with tire 0 and finish the lap in 2 seconds.
Lap 2: Continue with tire 0 and finish the lap in 2 * 3 = 6 seconds.
Lap 3: Change tires to a new tire 0 for 5 seconds and then finish the lap in another 2 seconds.
Lap 4: Continue with tire 0 and finish the lap in 2 * 3 = 6 seconds.
Total time = 2 + 6 + 5 + 2 + 6 = 21 seconds.
The minimum time to complete the race is 21 seconds.

Example 2:

Input: tires = [[1,10],[2,2],[3,4]], changeTime = 6, numLaps = 5
Output: 25
Explanation: 
Lap 1: Start with tire 1 and finish the lap in 2 seconds.
Lap 2: Continue with tire 1 and finish the lap in 2 * 2 = 4 seconds.
Lap 3: Change tires to a new tire 1 for 6 seconds and then finish the lap in another 2 seconds.
Lap 4: Continue with tire 1 and finish the lap in 2 * 2 = 4 seconds.
Lap 5: Change tires to tire 0 for 6 seconds then finish the lap in another 1 second.
Total time = 2 + 4 + 6 + 2 + 4 + 6 + 1 = 25 seconds.
The minimum time to complete the race is 25 seconds.

 

Constraints:

  • 1 <= tires.length <= 105
  • tires[i].length == 2
  • 1 <= fi, changeTime <= 105
  • 2 <= ri <= 105
  • 1 <= numLaps <= 1000

Solution Explanation

This problem asks for the minimum time to finish a race with a given number of laps, using tires with varying performance characteristics and a change time penalty. The solution uses dynamic programming to efficiently find the optimal strategy.

Understanding the Problem

Each tire has a base time (f) for the first lap and a rate of increase (r) for subsequent laps. The time for lap x with a given tire is f * r^(x-1). Switching tires adds a changeTime penalty. The goal is to minimize the total time to complete numLaps.

Dynamic Programming Approach

The dynamic programming solution cleverly avoids explicit exploration of all possible tire sequences. Instead, it focuses on the total time needed to complete a certain number of laps.

  1. Precomputation: First, for each tire, it precomputes the minimum time to complete 1 to 17 consecutive laps using that tire. This is because the time to complete a very large number of consecutive laps with one tire will almost certainly be much larger than a solution involving changing tires. 17 is chosen empirically: beyond this point, continuing with the same tire becomes increasingly inefficient. The results are stored in the cost array. cost[i] represents the minimum time to complete i consecutive laps using any single tire.

  2. DP Array: A dp array (named f in the code) of size numLaps + 1 stores the minimum time to complete i laps. dp[0] is initialized to -changeTime, reflecting the fact that there is no penalty before the first lap.

  3. Iteration: The code iterates from 1 to numLaps. For each i, it considers all possible ways to complete i laps:

    • It tries using j consecutive laps with the same tire (where j ranges from 1 to min(17, i)), using the precomputed cost[j].
    • It adds the minimum time to complete the previous i-j laps (dp[i-j]) and adds the time for these j laps (cost[j]).
    • The minimum time among all possible values of j is selected as dp[i].
    • Finally, the changeTime is added to dp[i] as the tire change penalty.

  4. Result: dp[numLaps] contains the minimum time to complete all laps.

Time Complexity Analysis

  • The precomputation step takes O(N * log(numLaps)) time, where N is the number of tires. This is because the loop for each tire will run until the time exceeds a threshold related to changeTime and the lap time will grow exponentially. The log factor comes from this exponential growth.

  • The dynamic programming step iterates numLaps times. The inner loop iterates at most 17 times in each iteration. Thus, the total time complexity of this step is O(numLaps).

Therefore, the overall time complexity is dominated by O(N * log(numLaps)). The space complexity is O(numLaps) due to the dp array. The cost array uses constant space.

Code Explanation (Python)

The Python code efficiently implements this dynamic programming approach. The use of inf (infinity) ensures that non-reachable states are handled correctly. The min() function is used to find the optimal time at each step.

The other languages (Java, C++, Go, TypeScript) present similar implementations, adapting the syntax to their respective environments. Key features like efficient array initialization and min/max operations remain consistent across all the solutions.