Show problems as
Classic problem #871HardArrayDynamic ProgrammingGreedyHeap (Priority Queue)

Minimum Number of Refueling Stops

Real-world version: Fewest Charging Halts
Tracked in this browser only
Read Minimum Number of Refueling Stops on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

An electric haul truck runs one straight corridor, entering at milepost 0 and finishing at milepost distance. Its pack begins the shift holding start_charge units, and one unit carries the truck exactly one milepost forward. The pack has no ceiling, so it can hold any amount of charge at once.

Charging pads sit along the corridor. Entry pads[i] = [milepost_i, units_i] says a pad waits at milepost_i holding units_i units of charge. Pulling into a pad tips that pad's whole reserve into the pack; partial draws are not possible, and the driver is free to roll past a pad without stopping. Pads are listed by increasing milepost. Coasting in with the pack reading exactly zero still counts as arriving, at a pad or at the corridor's end.

Work out the smallest number of pads the truck has to pull into so that it finishes the corridor. When no choice of pads carries it that far, the answer is -1.

Examples

Example 1

Input
distance = 90, start_charge = 25, pads = [[15, 20], [25, 50], [45, 25], [70, 30]]
Output
2

Roll past the pad at milepost 15 and take the 50 units waiting at milepost 25, which lifts the pack to 75 units of range. From there the pad at milepost 70 adds 30 more, reaching 105 units, which clears milepost 90 after only two halts.

Example 2

Input
distance = 60, start_charge = 10, pads = [[5, 1], [9, 1], [10, 50]]
Output
1

The opening 10 units already reach milepost 10, and the 50 units there lift the pack to 60 units of range, which clears the corridor.

Example 3

Input
distance = 30, start_charge = 5, pads = [[4, 3]]
Output
-1

The only pad lifts the pack to 8 units of range, which strands the truck at milepost 8 with nothing else in reach.

Constraints

  • 1 <= distance, start_charge <= 10^9
  • 0 <= pads.length <= 500
  • 1 <= milepost_i < milepost_i+1 < distance
  • 1 <= units_i < 10^9

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def fewest_charging_halts(distance: int, start_charge: int, pads: list[list[int]]) -> int:
Java
public int fewestChargingHalts(int distance, int startCharge, int[][] pads)

More on the same topics