Cheapest refuel plan: hints, no solution
Hard · Greedy
A refrigerated truck drives from kilometre 0 to a destination at kilometre distance. It burns one litre of fuel per kilometre, its tank holds at most capacity litres, and it leaves kilometre 0 with an empty tank. Fuel stops are listed in positions, given as strictly increasing kilometre markers below distance, and prices[i] is the cost per litre at stop i. At a stop you may buy any whole number of litres as long as the tank does not overflow. The truck may arrive with no fuel left. Return the minimum total cost to reach the destination, or -1 if it cannot be done. Aim for O(n) or O(n log n) in the number of stops.
Examples
- Input
- capacity = 10, distance = 25, positions = [0, 8, 15, 20], prices = [5, 3, 6, 2]
- Output
- 92
- Note
- Buy 8 litres at kilometre 0, fill the tank at the cheap stop at 8, then buy 2 litres at 15 and 5 at 20.
- Input
- capacity = 5, distance = 12, positions = [0, 4, 11], prices = [1, 1, 1]
- Output
- -1
- Note
- The gap from kilometre 4 to kilometre 11 is 7, more than a full tank.
- Input
- capacity = 6, distance = 6, positions = [0], prices = [7]
- Output
- 42
Constraints
- 1 <= capacity <= 1000000 and 1 <= distance <= 1000000
- 0 <= positions.length <= 100000, strictly increasing, each below distance
- 1 <= prices[i] <= 1000
Hint 1: a nudge
At a given stop, would you ever buy more fuel than you need to reach the next stop? What would make buying extra worthwhile?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.