Minimum Time to Finish the Race

Minimum Time to Finish the Race

What is this problem about?

The Minimum Time to Finish the Race problem gives you a set of tire types, each with a starting speed and degradation factor. You can change tires at any point (at a fixed cost). The goal is to find the minimum total time to complete exactly n laps. This Minimum Time to Finish the Race coding problem is a dynamic programming problem that first precomputes optimal single-tire lap times, then builds a full-race DP.

Why is this asked in interviews?

Google asks this hard problem because it requires two-layer DP: first, find the best time to do k consecutive laps on any single tire without changing (including precomputation of when switching tires becomes beneficial). Second, build a DP over total laps optimizing when to switch. The array and dynamic programming interview pattern is the core, and the problem tests layered optimization.

Algorithmic pattern used

Two-phase DP. Phase 1: For each tire type, precompute best[k] = minimum time to run k consecutive laps on that tire (stop when the degraded time exceeds the cost of a fresh tire change + 1 lap). Phase 2: DP over laps: dp[i] = minimum time to complete i laps. Transition: dp[i] = min over all j (dp[i-j] + changeTime + best[j]), representing completing the last j laps on a fresh tire. Final answer: dp[n] - changeTime (don't pay for a change after the last tire).

Example explanation

Tires: [f=2, r=3]: laps take 2, 6, 18, ... seconds. changeTime = 5.

• best[1]=2, best[2]=8 (2+6), best[3] > changeTime+2 so stop at 2 laps useful.
• dp[1] = changeTime + 2 = 7. dp[2] = min(dp[1]+changeTime+best[1], changeTime+best[2]) = min(19, 13). dp[n]...
• Final answer after subtracting changeTime.

Common mistakes candidates make

• Not precomputing the per-tire consecutive lap costs, trying to embed them into the main DP.
• Forgetting to subtract the final changeTime from the answer.
• Allowing too many consecutive laps when degradation makes switching cheaper.
• Indexing DP from 0 instead of 1.

Interview preparation tip

Problems involving "switch resources at optimal times" often decompose into two DPs: one for the cost of using one resource continuously for k units, and one for the overall optimization with switching. Recognize this two-phase structure and implement them separately. After computing the best[k] table in O(numTires * maxLaps), the main DP runs in O(n * maxLaps). This clean separation reduces implementation complexity and is a professional coding practice valued in senior interviews.