Welcome to Subscribe On Youtube
2188. Minimum Time to Finish the Race
Description
You are given a 0indexed 2D integer array tires
where tires[i] = [f_{i}, r_{i}]
indicates that the i^{th}
tire can finish its x^{th}
successive lap in f_{i} * r_{i}^{(x1)}
seconds.
 For example, if
f_{i} = 3
andr_{i} = 2
, then the tire would finish its1^{st}
lap in3
seconds, its2^{nd}
lap in3 * 2 = 6
seconds, its3^{rd}
lap in3 * 2^{2} = 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 <= 10^{5}
tires[i].length == 2
1 <= f_{i}, changeTime <= 10^{5}
2 <= r_{i} <= 10^{5}
1 <= numLaps <= 1000
Solutions

class Solution { public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) { final int inf = 1 << 30; int[] cost = new int[18]; Arrays.fill(cost, inf); for (int[] e : tires) { int f = e[0], r = e[1]; int s = 0, t = f; for (int i = 1; t <= changeTime + f; ++i) { s += t; cost[i] = Math.min(cost[i], s); t *= r; } } int[] f = new int[numLaps + 1]; Arrays.fill(f, inf); f[0] = changeTime; for (int i = 1; i <= numLaps; ++i) { for (int j = 1; j < Math.min(18, i + 1); ++j) { f[i] = Math.min(f[i], f[i  j] + cost[j]); } f[i] += changeTime; } return f[numLaps]; } }

class Solution { public: int minimumFinishTime(vector<vector<int>>& tires, int changeTime, int numLaps) { int cost[18]; memset(cost, 0x3f, sizeof(cost)); for (auto& e : tires) { int f = e[0], r = e[1]; int s = 0; long long t = f; for (int i = 1; t <= changeTime + f; ++i) { s += t; cost[i] = min(cost[i], s); t *= r; } } int f[numLaps + 1]; memset(f, 0x3f, sizeof(f)); f[0] = changeTime; for (int i = 1; i <= numLaps; ++i) { for (int j = 1; j < min(18, i + 1); ++j) { f[i] = min(f[i], f[i  j] + cost[j]); } f[i] += changeTime; } return f[numLaps]; } };

class Solution: def minimumFinishTime( self, tires: List[List[int]], changeTime: int, numLaps: int ) > int: cost = [inf] * 18 for f, r in tires: i, s, t = 1, 0, f while t <= changeTime + f: s += t cost[i] = min(cost[i], s) t *= r i += 1 f = [inf] * (numLaps + 1) f[0] = changeTime for i in range(1, numLaps + 1): for j in range(1, min(18, i + 1)): f[i] = min(f[i], f[i  j] + cost[j]) f[i] += changeTime return f[numLaps]

func minimumFinishTime(tires [][]int, changeTime int, numLaps int) int { const inf = 1 << 30 cost := [18]int{} for i := range cost { cost[i] = inf } for _, e := range tires { f, r := e[0], e[1] s, t := 0, f for i := 1; t <= changeTime+f; i++ { s += t cost[i] = min(cost[i], s) t *= r } } f := make([]int, numLaps+1) for i := range f { f[i] = inf } f[0] = changeTime for i := 1; i <= numLaps; i++ { for j := 1; j < min(18, i+1); j++ { f[i] = min(f[i], f[ij]+cost[j]) } f[i] += changeTime } return f[numLaps] }

function minimumFinishTime(tires: number[][], changeTime: number, numLaps: number): number { const cost: number[] = Array(18).fill(Infinity); for (const [f, r] of tires) { let s = 0; let t = f; for (let i = 1; t <= changeTime + f; ++i) { s += t; cost[i] = Math.min(cost[i], s); t *= r; } } const f: number[] = Array(numLaps + 1).fill(Infinity); f[0] = changeTime; for (let i = 1; i <= numLaps; ++i) { for (let j = 1; j < Math.min(18, i + 1); ++j) { f[i] = Math.min(f[i], f[i  j] + cost[j]); } f[i] += changeTime; } return f[numLaps]; }