LeetCode 871: Minimum Number of Refueling Stops

Explanation:

To solve this problem, we can use a priority queue to keep track of the gas stations that we can refuel at. We iterate over the stations and as long as our current fuel is not enough to reach the next station, we refuel from the station with the highest amount of fuel we encountered so far. We keep track of the number of stops we make and return it as the result.

Detailed steps:

1. Initialize variables: stops = 0 (number of stops), currPos = 0 (current position), currFuel = startFuel.
2. Initialize a priority queue maxHeap to store the gas stations in descending order of fuel.
3. Iterate over the gas stations:
   • If we can reach the next station with the current fuel, update currPos and currFuel accordingly.
   • If we can't reach the next station, refuel from the stations in maxHeap until we can reach the next station.
   • If we can't reach the next station even after refueling, return -1.
4. Return the number of stops made.

Time Complexity: O(n log n) - where n is the number of gas stations. Space Complexity: O(n) - for the priority queue.

:

import java.util.PriorityQueue;

class Solution {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        int stops = 0, currPos = 0, currFuel = startFuel;
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        for (int[] station : stations) {
            int stationPos = station[0];
            int stationFuel = station[1];

            while (currFuel < stationPos - currPos) {
                if (maxHeap.isEmpty()) return -1;
                currFuel += maxHeap.poll();
                stops++;
            }

            maxHeap.offer(stationFuel);
            currPos = stationPos;
        }

        while (currFuel < target - currPos) {
            if (maxHeap.isEmpty()) return -1;
            currFuel += maxHeap.poll();
            stops++;
        }

        return stops;
    }
}