Minimum Number of Refueling Stops

January 25, 2024

Problem Statement #

A car travels from a starting position to a destination, a distance of target miles. There are gas stations along the way. The car starts with an initial tank of fuel, and it can travel startFuel miles on a full tank. You are given an integer target, an integer startFuel, and an array stations where stations[i] = [position_i, fuel_i] indicates that the i-th gas station is position_i miles along the way and has fuel_i liters of gas. Return the minimum number of refueling stops the car must make to reach its destination. If it is impossible to reach the destination, return -1.

Example:

1. Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]] Output: 2 Explanation:
   • Start with 10 liters of fuel.
   • Drive to the first station at 10 miles, refill 60 liters.
   • Drive to the third station at 30 miles, refill 30 liters.
   • Drive to the destination. Total refueling stops = 2.

Solution Approach #

The solution involves using a max heap to store fuel from the gas stations and using it only when necessary.

Algorithm Steps #

1. Sort the stations array based on their position.
2. Use a max heap to keep track of the fuel amounts available at the stations passed.
3. Iterate through the stations, adding their fuel to the heap when passed.
4. If at any point the car cannot reach the next station (or the target), refill with the largest available fuel from the heap.
5. Keep track of the number of refuels and return it at the end.

Code (Python) #

import heapq

def minRefuelStops(target, startFuel, stations):
    stations.append((target, float('inf')))
    heap, stops, prev = [], 0, 0
    fuel = startFuel

    for location, capacity in stations:
        fuel -= location - prev
        while heap and fuel < 0:
            fuel += -heapq.heappop(heap)
            stops += 1
        if fuel < 0: return -1
        heapq.heappush(heap, -capacity)
        prev = location

    return stops

# Test the function
print(minRefuelStops(100, 10, [[10,60],[20,30],[30,30],[60,40]]))  # Output: 2

Time Complexity #

O(n log n), where n is the number of fuel stations. Heap operations contribute to the log n factor.

Space Complexity #

O(n), for the max heap used to store fuel amounts.