Skip to interview prep
Apexed

340. A car with a range of R miles on a full tank drives along a road with fuel stations at known positions. How do you minimise the number of refuelling stops?

MediumGreedy algorithms

Technical
Show model answer

Drive as far as possible: from your current position, stop at the farthest station you can reach before the tank runs out, refill, and repeat. If the next station is more than R beyond the current one, the trip is impossible. After sorting stations by position this is a single O(n) scan with O(1) space.

Exchange argument: take any optimal plan whose first stop is earlier than the greedy's first stop. Moving that stop forward to the greedy's station keeps the plan feasible (you can still reach the next stop because you start later with a full tank) and does not add stops, so by induction greedy matches optimal. If stations hold different amounts of fuel rather than giving full refills, keep a max-heap of fuel at stations you have passed and take the largest one only when you would otherwise run dry, for O(n log n).

A car with a range of R miles on a full tank drives along a road with fuel stations at known positions. How do you minimise the number of refuelling stops — Dat