Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2188.html

2188. Minimum Time to Finish the Race (Hard)

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

Similar Questions:

Solution 1. DP

The best[i] is the least time we need to finish i+1 laps using a single tire. For each tire, we try to update the best values with it.

The dp part is doing knapsack using the best values to get the total numLaps laps.

// OJ: https://leetcode.com/problems/minimum-time-to-finish-the-race/
// Time: O(N * numLaps)
// Space: O(numLaps)
class Solution {
public:
    int minimumFinishTime(vector<vector<int>>& A, int change, int numLaps) {
        int N = A.size(), len = 0;
        vector<long> best(numLaps, LONG_MAX), dp(numLaps + 1, INT_MAX);
        for (int i = 0; i < N; ++i) {
            long f = A[i][0], r = A[i][1], sum = change, p = 1; // We assume we also need `change` time to use the first tire so that we don't need to treat the first tire as a special case
            for (int j = 0; j < numLaps; ++j) {
                sum += f * p;
                if (f * p >= f + change) break; // If using the same tire takes no less time than changing the tire, stop further using the current tire
                best[j] = min(best[j], sum);
                len = max(len, j + 1);
                p *= r;
            }
        }
        dp[0] = 0; // dp[i + 1] is the minimum time to finish `numLaps` laps
        for (int i = 0; i < numLaps; ++i) {
            for (int j = 0; j < len && i - j >= 0; ++j) { // try using the same tire in the last `j+1` laps
                dp[i + 1] = min(dp[i + 1], dp[i - j] + best[j]);
            }
        }
        return dp[numLaps] - change; // minus the `change` we added to the first tire
    }
};

All Problems

All Solutions