#2188
Minimum Time to Finish the Race
master · 1610 · lc hard +32 · verified · 43.3% accepted · 602 likes · top 25%
Description
You are given a 0-indexed 2D integer array tires where tires[i] = [fi, ri] means the ith tire completes its xth consecutive lap in fi * ri^(x-1) seconds.
- For example, if fi = 3 and ri = 2, the tire finishes its 1st lap in 3 seconds, its 2nd lap in 6 seconds, its 3rd in 12 seconds, and so on.
You are also given an integer changeTime and an integer numLaps. Each tire change takes changeTime seconds, and you start the race with any tire. You have unlimited copies of each tire.
Return the minimum time to finish all numLaps laps.
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.
Code
1
2
3