Car starts with startFuel, reach target using stations. Minimize number of refueling stops.
Input: target=100, startFuel=10, stations=[[10,60],[20,30],[30,30],[60,40]] → Output: 2
Input: target=1, startFuel=1, stations=[] → Output: 0
Greedy with max-heap: drive as far as possible. When out of fuel, greedily refuel at station with most fuel seen so far.
- Add all passed stations to max-heap by fuel
- When current fuel < next required distance
- Poll max from heap and add to fuel (stops++)
- If heap empty but still cant reach, return -1
- Return stops count
public int minRefuelStops(int target, int startFuel, int[][] stations) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
int fuel = startFuel, stops = 0, prev = 0;
for (int[] s : stations) {
fuel -= s[0] - prev;
prev = s[0];
while (fuel < 0 && !pq.isEmpty()) {
fuel += pq.poll();
stops++;
}
if (fuel < 0) return -1;
pq.offer(s[1]);
}
fuel -= target - prev;
while (fuel < 0 && !pq.isEmpty()) {
fuel += pq.poll();
stops++;
}
return fuel >= 0 ? stops : -1;
}
- Time Complexity: O(n log n)
- Space Complexity: O(n)