2188. Minimum Time to Finish the Race

Hard

493

21

You are given a **0-indexed** 2D integer array `tires`

where `tires[i] = [f`

indicates that the _{i}, r_{i}]`i`

tire can finish its ^{th}`x`

successive lap in ^{th}`f`

seconds._{i} * r_{i}^{(x-1)}

- For example, if
`f`

and_{i}= 3`r`

, then the tire would finish its_{i}= 2`1`

lap in^{st}`3`

seconds, its`2`

lap in^{nd}`3 * 2 = 6`

seconds, its`3`

lap in^{rd}`3 * 2`

seconds, etc.^{2}= 12

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 = 4Output:21Explanation: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 = 5Output:25Explanation: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`

Accepted

10K

Submissions

24.1K

Acceptance Rate

41.6%

Seen this question in a real interview before?

1/4

Yes

No

Discussion (0)

Related Topics

Copyright ©️ 2023 LeetCode All rights reserved