Leetcode

Minimum Time to Finish the Race

May 26, 2022 by aAshish

  • Time:O(|\texttt{tires}| + \texttt{numLaps}^2)
  • Space:O(\texttt{numLaps}^2)

C++

 
class Solution {
 public:
  int minimumFinishTime(vector<vector<int>>& tires, int changeTime,
                        int numLaps) {
    // singleTire[i] := min time to finish i laps w/o changing tire
    vector<int> singleTire(numLaps + 1, INT_MAX / 2);
    // dp[i] := min 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) {
        // time to use the same tire for next lap >=
        // 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;
  }
};

JAVA

 
class Solution {
  public int minimumFinishTime(int[][] tires, int changeTime, int numLaps) {
    // singleTire[i] := min time to finish i laps w/o changing tire
    int[] singleTire = new int[numLaps + 1];
    // dp[i] := min 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) {
        // time to use the same tire for next lap >=
        // 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;
  }
}

Python

 
class Solution:
  def minimumFinishTime(self, tires: List[List[int]], changeTime: int, numLaps: int) -> int:
    # singleTire[i] := min time to finish i laps w//o changing tire
    singleTire = [math.inf] * (numLaps + 1)
    # dp[i] := min 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):
        # time to use the same tire for next lap >=
        # 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