We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Refueling Stops

Difficulty: Hard

Problem Description

A car travels from a starting position to a destination which is target miles east of the starting position. There are gas stations along the way, represented as an array stations, where stations[i] = [position_i, fuel_i] indicates that the i-th gas station is position_i miles east of the starting position and has fuel_i liters of gas. The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it. It uses one liter of gas per one mile that it drives. When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car. Return the minimum number of refueling stops the car must make in order to reach its destination. If it cannot reach the destination, return -1.

Key Insights

  • The car can reach the destination without refueling if startFuel is greater than or equal to target.
  • If the car cannot reach the first gas station, it cannot proceed at all.
  • A greedy approach using a max-heap to choose the best gas stations to refuel from can minimize the number of stops.
  • The algorithm must keep track of the current fuel level and the distance traveled.

Space and Time Complexity

Time Complexity: O(n log n) - where n is the number of gas stations, due to the use of the max-heap for efficient refueling. Space Complexity: O(n) - for storing the gas stations in an array, and O(n) for the max-heap.

Solution

To solve the problem, we utilize a greedy algorithm combined with a max-heap (priority queue) to manage the fuel from gas stations. The key steps are:

  1. Iterate through the gas stations and keep track of the current fuel level and distance traveled.
  2. When the current fuel is insufficient to reach the next station or the destination, utilize the max-heap to refuel from the gas stations visited so far, starting from the one that provides the most fuel.
  3. Count the number of refueling stops made until reaching the destination or determining that it is not possible.

Code Solutions

import heapq

def minRefuelStops(target, startFuel, stations):
    stations.append((target, 0))  # Add the target as a station with 0 fuel
    max_heap = []
    fuel = startFuel
    prev_pos = 0
    stops = 0
    
    for pos, fuel_amount in stations:
        fuel -= (pos - prev_pos)  # Reduce fuel by the distance to the next station
        while fuel < 0 and max_heap:  # While we can't reach the next station
            fuel += -heapq.heappop(max_heap)  # Refuel with the best option
            stops += 1
        if fuel < 0:  # If still not enough fuel, return -1
            return -1
        heapq.heappush(max_heap, -fuel_amount)  # Push current station's fuel to max-heap
        prev_pos = pos  # Update previous position to current
    
    return stops
← Back to All Questions