Skip to content

2188. Minimum Time to Finish the Race 👍

Approach 1: Two variables

  • Time: $O(|\texttt{tires}| + \texttt{numLaps}^2)$
  • Space: $O(\texttt{numLaps})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
 public:
  int minimumFinishTime(vector<vector<int>>& tires, int changeTime,
                        int numLaps) {
    // singleTire[i] := the minimum time to finish i laps without changing tire
    vector<int> singleTire(numLaps + 1, INT_MAX / 2);
    // dp[i] := the minimum time to finish i laps
    vector<int> dp(numLaps + 1, INT_MAX / 2);

    for (int i = 0; i < tires.size(); ++i) {
      const int f = tires[i][0];
      const int r = tires[i][1];
      int sumSecs = 0;
      int rPower = 1;
      for (int j = 1; j <= numLaps; ++j) {
        // the time to use the same tire for the next lap >=
        // the time to change a new tire + f
        if ((long)f * rPower >= changeTime + f)
          break;
        sumSecs += f * rPower;
        rPower *= r;
        singleTire[j] = min(singleTire[j], sumSecs);
      }
    }

    dp[0] = 0;
    for (int i = 1; i <= numLaps; ++i)
      for (int j = 1; j <= i; ++j)
        dp[i] = min(dp[i], dp[i - j] + changeTime + singleTire[j]);

    return dp[numLaps] - changeTime;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
  public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {
    // singleTire[i] := the minimum time to finish i laps without changing tire
    int[] singleTire = new int[numLaps + 1];
    // dp[i] := the minimum time to finish i laps
    int[] dp = new int[numLaps + 1];

    Arrays.fill(singleTire, Integer.MAX_VALUE / 2);
    Arrays.fill(dp, Integer.MAX_VALUE / 2);

    for (int i = 0; i < tires.length; ++i) {
      final int f = tires[i][0];
      final int r = tires[i][1];
      int sumSecs = 0;
      int rPower = 1;
      for (int j = 1; j <= numLaps; ++j) {
        // the time to use the same tire for the next lap >=
        // the time to change a new tire + f
        if ((long) f * rPower >= changeTime + f)
          break;
        sumSecs += f * rPower;
        rPower *= r;
        singleTire[j] = Math.min(singleTire[j], sumSecs);
      }
    }

    dp[0] = 0;
    for (int i = 1; i <= numLaps; ++i)
      for (int j = 1; j <= i; ++j)
        dp[i] = Math.min(dp[i], dp[i - j] + changeTime + singleTire[j]);

    return dp[numLaps] - changeTime;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
  def minimumFinishTime(
      self,
      tires: list[list[int]],
      changeTime: int,
      numLaps: int,
  ) -> int:
    # singleTire[i] := the minimum time to finish i laps without changing tire
    singleTire = [math.inf] * (numLaps + 1)
    # dp[i] := the minimum time to finish i laps
    dp = [math.inf] * (numLaps + 1)

    for i, (f, r) in enumerate(tires):
      sumSecs = 0
      rPower = 1
      for j in range(1, numLaps + 1):
        # the time to use the same tire for the next lap >=
        # the time to change a new tire + f
        if f * rPower >= changeTime + f:
          break
        sumSecs += f * rPower
        rPower *= r
        singleTire[j] = min(singleTire[j], sumSecs)

    dp[0] = 0
    for i in range(1, numLaps + 1):
      for j in range(1, i + 1):
        dp[i] = min(dp[i], dp[i - j] + changeTime + singleTire[j])

    return dp[numLaps] - changeTime

Approach 2: One variable

  • Time: $O(|\texttt{tires}| \log\texttt{numLaps} + \texttt{numLaps}^2)$
  • Space: $O(\texttt{numLaps})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int minimumFinishTime(vector<vector<int>>& tires, int changeTime,
                        int numLaps) {
    // dp[i] := the minimum time of the first i laps
    vector<int> dp(numLaps + 1, INT_MAX);

    for (const vector<int>& t : tires)
      for (int seconds = t[0], secondsSum = t[0], lapCount = 1;
           seconds < t[0] + changeTime && lapCount < dp.size();
           seconds *= t[1], ++lapCount, secondsSum += seconds)
        dp[lapCount] = min(secondsSum, dp[lapCount]);

    for (int i = 2; i <= numLaps; ++i)
      for (int j = 1; j * 2 <= i; ++j)
        dp[i] = min(dp[i], dp[j] + dp[i - j] + changeTime);

    return dp[numLaps];
  }
};