871.minimum-number-of-refueling-stops.md

871. Minimum Number of Refueling Stops

Heap + Greedy

We want to refuel as few times as possible, we can solve this problem with greedy approach. The best greedy strategy is to refuel at the station with the most fuel ONLY when we're stuck. We always collect fuel as we pass stations (by adding to the heap), and only refuel when we have insufficient fuel to fo forward, and refuel with the most fuel passed stations so far.

• 找最低加油次數，那就能不加油就不加，什麼時候要加油？就是不得不加的時候，現在不加就到不了下一個目的地。(貪心) 而且一定是先選最大油量的去加，一直加直到可以到達下一站或終點。
• 事后诸葛亮体现在我们是我們到達加油站的時候都先不加，等到没油了才去想应该在之前的某个站加油。这个事后诸葛亮本质上解决的是，基于当前信息无法获取最优解，我们必须掌握全部信息之后回溯。 (Source)
• 我們開車經過所有加油站，都先把油放到後車廂備著，等到開到沒油的時候，就加上之前拿到的最大桶，直到終點看看用了幾桶。
• My original thought is to refuel whenever we can, then review all the previous refueling stations, and see if we can skip some of them. But the correct way is to skip as much as possible, and only refuel when we're stuck.

fun minRefuelStops(target: Int, startFuel: Int, stations: Array<IntArray>): Int {
    val maxHeap = PriorityQueue<Int>(reverseOrder())
    var remainingFuel = startFuel
    var ans = 0
    var i = 0
    while (remainingFuel < target) {
        // Try to collect all the fuel we can get from the stations we passed until we can't reach the next station
        while (i < stations.size && stations[i][0] <= remainingFuel) {
            maxHeap.add(stations[i][1])
            i++
        }

        // Now we're stuck, we need to refuel:
        // There is no more fuel to refuel, we can't reach the destination
        if (maxHeap.isEmpty()) return -1

        // Refuel with the most fuel passed stations so far
        remainingFuel += maxHeap.poll()
        ans++
    }
    return ans
}

// Or equivalently, we record the last position we can reach, and refuel when we're stuck.
fun minRefuelStops(target: Int, startFuel: Int, stations: Array<IntArray>): Int {
    val maxHeap = PriorityQueue<Int>(reverseOrder())
    var last = 0
    var remainingFuel = startFuel
    var ans = 0
    for ((i, fuel) in stations) {
        remainingFuel -= (i - last)

        while (remainingFuel < 0 && maxHeap.isNotEmpty()) {
            remainingFuel += maxHeap.poll()
            ans++
        }
        if (remainingFuel < 0) return -1

        maxHeap.add(fuel)
        last = i
    }

    // Check the final leg to target
    remainingFuel -= (target - last)
    while (remainingFuel < 0 && maxHeap.isNotEmpty()) {
        remainingFuel += maxHeap.poll()
        ans++
    }
    if (remainingFuel < 0) return -1

    return ans
}

// Or another way to think about it: BFS template with priority queue
fun minRefuelStops(target: Int, startFuel: Int, stations: Array<IntArray>): Int {
    var i = 0       // station index
    var fuel = 0    // current fuel (or position)
    var count = 0   // number of refueling (answer)
    val queue = PriorityQueue<Int>(reverseOrder())
    queue.add(startFuel)
    while (queue.isNotEmpty()) {
        fuel += queue.poll() // Dequeue the node
        if (fuel >= target) return count // Check if we've reached the target

        // Enqueue all the adjacent node
        while (i < stations.size && stations[i][0] <= fuel) {
            queue.add(stations[i][1])
            i++
        }

        // Update the BFS level
        count++
    }
    return -1
}

Dynamic Programming

Let dp[i] to be the furthest position we can reach with i times of refueling. So for each station, we can refuel: dp[i + 1] = max(dp[i + 1], dp[i] + stations[i][1]) if we can reach the station (dp[i] >= stations[i][0]). Then we return the first i so that dp[i] >= target:

TODO: Try to understand why we iterate reversely.

• dp[j + 1] gets updated based on newly updated dp[j] from this same loop. This causes overcounting. Why? Because: The dp[j] you're reading may have just been updated by an earlier j-1 in the same loop!

fun minRefuelStops(target: Int, startFuel: Int, stations: Array<IntArray>): Int {
    val dp = IntArray(stations.size + 1)
    dp[0] = startFuel
    for (i in stations.indices) {
        val (position, fuel) = stations[i]
        // NOTE: We need to iterate from the end to the start, because we need to use the previous state to update the current state
        // If we iterate from the start to the end, we will use the updated state to update the current state, which is not correct
        for (j in i downTo 0) {
            if (dp[j] >= position) {
                dp[j + 1] = maxOf(dp[j + 1], dp[j] + fuel)
            }
        }
    }
    for (i in dp.indices) {
        if (dp[i] >= target) return i
    }
    return -1
}

My Original Implementation (WA)

Key idea: Refuel greedily, recheck which previous refueling is unnecessary. 假設現在油足夠，可以超過下一個加油站，但是我們一樣先加油，因為不知道後面有沒有足夠加油站和油量。

Breakdown

1. How to simulate the process of driving regardless of the number of refuel?
2. How to detect unreachable destination?
3. How to check if previous refuel is necessary: Not at target, and no station anymore or can't reach station

Steps

position i → gas j: consume j - i fuel, refuel gas[j], count++, check if we can remove any previous refuel.

1. Maintain current position, fuel (maximum reachable position), gas index.
2. Keep moving until current position + fuel ≥ destination.
3. Otherwise, use fuel to get to gas to refuel:
   • Refuel
   • Check any previous refuel is necessary

val position: `i`
val fuel: `x`
val station: `j`

while (i + x < target && has station) {
    i = i + x // move to next station
    x = 0
    // refuel
    while (j < len(s) && s[j] < i) {
        x += s[j]
        j++
    }
}

fun hasStation() = j < len(s) && i + x >= s[j]

Reflections

In greedy approach, we don't always want to refuel as soon as we can. Instead, we always delay refueling until we're required to do so, then always pick the station with the most fuel. So the idea is not "refuel whenever we can", but "refuel only when we're stuck".