Min Number of Refueling Stops
Ramayana — Hanuman's Flight — Reach Lanka with the Fewest Refueling Stops
लक्ष्य तक — न्यूनतम पड़ाव। जब ईंधन खत्म — सबसे बड़ा पिछला ईंधन भरो॥
*To the target — minimum stops. When fuel runs out — refuel from the largest past station.*
The Story
Starting from position 0 with `startFuel`, reach `target`. Stations at positions with fuel amounts. Find minimum stops to reach target, or -1 if impossible.
For `target=100`, `startFuel=10`, `stations=[[10,60],[20,30],[30,30],[60,40]]`: answer=2.
**Greedy with Max-Heap — "Lazy Refueling":** - Drive as far as possible on current fuel - As you pass stations, add their fuel to a max-heap (available but not yet used) - When you run out of fuel: retroactively refuel from the largest available station (greedy: always pick biggest) - If heap is empty and you can't reach target: return -1
```java PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->b-a); // Max-heap int fuel=startFuel, stops=0, i=0; while (fuel < target) { // Add all reachable stations to the heap while (i < stations.length && stations[i][0] <= fuel) { pq.offer(stations[i][1]); i++; } if (pq.isEmpty()) return -1; // Can't reach anywhere fuel += pq.poll(); // Retroactively refuel from best station stops++; } return stops; ```
Trace `target=100`, `startFuel=10`, `[[10,60],[20,30],[30,30],[60,40]]`: - fuel=10 < 100. Stations with pos≤10: [10,60] → pq=[60]. Poll 60: fuel=70, stops=1 - fuel=70 < 100. Stations with pos≤70: [20,30],[30,30],[60,40] → pq=[40,30,30]. Poll 40: fuel=110, stops=2 - fuel=110 ≥ 100 → return 2 ✓
The DP Approach
dp[i] = max fuel reachable using exactly i stops. dp[0]=startFuel. Transition: dp[j+1] = max(dp[j] + stations[k].fuel) for all k reachable with dp[j]. O(n²).
public int minRefuelStopsDP(int target, int startFuel, int[][] stations) {
int n=stations.length;
long[] dp=new long[n+1];
dp[0]=startFuel;
for (int i=0;i<n;i++) for (int j=i;j>=0;j--)
if (dp[j]>=stations[i][0])
dp[j+1]=Math.max(dp[j+1],dp[j]+stations[i][1]);
for (int i=0;i<=n;i++) if (dp[i]>=target) return i;
return -1;
}Hanuman's Retroactive Best-Refuel Wisdom
public int minRefuelStops(int target, int startFuel, int[][] stations) {
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
int fuel = startFuel, stops = 0, i = 0;
while (fuel < target) {
while (i < stations.length && stations[i][0] <= fuel) {
pq.offer(stations[i][1]);
i++;
}
if (pq.isEmpty()) return -1;
fuel += pq.poll();
stops++;
}
return stops;
}Step-by-Step Walkthrough
target=1, startFuel=1, [] fuel=1 >= 1 → return 0 (no stops needed) ✅
Deep Insight
**Why retroactive greedy works:** Instead of deciding AT each station whether to refuel, we decide WHEN WE RUN OUT. This is greedy: when stranded, pick the biggest fuel we've passed. This is always optimal because: - A bigger tank refuel = fewer future stops needed - Any stop we skipped in the real timeline could have been a stop — retroactively using it now achieves the same effect as stopping then
**Connection to hp-11 (CPU Scheduler):** Both use a max-heap to greedily pick the best available resource when needed — not greedily at every step but only when forced (running out of fuel / filling an idle slot).
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | DP with n+1 states |
| Optimal | O(n log n) | O(n) | Each station added/removed from heap at most once |
Pattern Recognition
✅ Retroactive greedy: add passed stations to max-heap ✅ When stranded: poll max from heap (retroactive refuel) ✅ Count stops; return -1 if heap empty when stranded ✅ Classic 'lazy greedy' with max-heap **LeetCode Trigger Phrases:** → "minimum refueling stops" → Retroactive greedy with max-heap → 'Use best available resource when forced'
Bhagavad Gita 2.11
गतासूनगतासूंश्च नानुशोचन्ति पण्डिताः।
The wise grieve neither for the living nor for the dead.
Connection: Hanuman doesn't anxiously stop at every station, wasting precious momentum. He flies as far as possible, and only when truly stranded does he retroactively choose the optimal past refuel point. Like the wise person who acts with clarity rather than anxious precaution at every step, the algorithm maintains forward momentum and only intervenes when necessary — choosing the best available option from accumulated wisdom (the passed stations in the heap).