Minimum Skips to Arrive at Meeting On Time LeetCode solution in JavaScript

1
var minSkips = function (dist, speed, hoursBefore) {
2
  // calculates the time needed to rest
3
  const getRestTime = (timeFinished) => {
4
    if (timeFinished === Infinity) return 0;
5
    return (speed - (timeFinished % speed)) % speed;
6
  };
7

8
  // dp is a n x n matrix with
9
  // dp[destinationIndex][numRestsSkipped] = timeTaken
10
  //
11
  // destinationIndex: the index of the destination being observed
12
  // numRestsSkipped: number of rests taken
13
  // timeTaken: minimum time taken to travel to destination taking numRests number of rests
14
  const dp = [...dist].map(() => new Array(dist.length).fill(Infinity));
15

16
  // start with the first stop
17
  dp[0][0] = dist[0] + getRestTime(dist[0]); // took a rest at the first destination
18
  dp[0][1] = dist[0]; // did not take a rest at the first destination
19

20
  for (let distIdx = 1; distIdx < dist.length; distIdx++) {
21
    const distance = dist[distIdx];
22
    let timeToDestWithoutrest = dp[distIdx - 1][0] + distance;
23
    dp[distIdx][0] = timeToDestWithoutrest + getRestTime(timeToDestWithoutrest);
24
    for (
25
      let numRestsSkipped = 1;
26
      numRestsSkipped <= distIdx + 1;
27
      numRestsSkipped++
28
    ) {
29
      // calculate the time if taking a rest here
30
      timeToDestWithoutrest = dp[distIdx - 1][numRestsSkipped] + distance;
31
      const didRestTimeToDest =
32
        timeToDestWithoutrest + getRestTime(timeToDestWithoutrest);
33

34
      // calculate the time without resting here
35
      const didntRestTimeToDest =
36
        dp[distIdx - 1][numRestsSkipped - 1] + distance;
37

38
      // store the best time in the dp
39
      dp[distIdx][numRestsSkipped] = Math.min(
40
        dp[distIdx][numRestsSkipped],
41
        didRestTimeToDest,
42
        didntRestTimeToDest
43
      );
44
    }
45
  }
46

47
  // find the minimum number of rests visiting all the destinations
48
  const speedHours = speed * hoursBefore;
49
  for (let numRests = 0; numRests < dist.length; numRests++) {
50
    if (dp[dist.length - 1][numRests] <= speedHours) {
51
      return numRests;
52
    }
53
  }
54
  return -1;
55
};