# 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**:

- 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 #

- Sort the
`stations`

array based on their position. - Use a max heap to keep track of the fuel amounts available at the stations passed.
- Iterate through the stations, adding their fuel to the heap when passed.
- If at any point the car cannot reach the next station (or the target), refill with the largest available fuel from the heap.
- 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.