0169HardArrayDynamic ProgrammingGreedyHeap (Priority Queue)

Fewest Charging Halts

Tracked in this browser only

Trains the technique from

LeetCode 871Minimum Number of Refueling Stops

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a 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)

The intended approach

Time O(n log n)Space O(n)

Where a pad is drawn from does not matter, only that the truck had already reached it, so treat every pad the truck rolls past as charge banked for later. Sweep the corridor keeping the reach the pack currently affords: bank each pad whose milepost falls inside that reach, and whenever the reach still falls short of the corridor's end, spend one halt on the fattest banked pad, since any smaller pad would push the reach less far for the same halt. Running out of banked pads while short of the end proves no route exists.

Pythonentry point: fewest_charging_halts

def fewest_charging_halts(distance, start_charge, pads):
    # Time: O(n log n) -- every pad is banked once and drawn at most once.
    # Space: O(n) -- the reserve heap of banked but unused pads.
    import heapq
    reserve = []
    charge = start_charge
    halts = 0
    i = 0
    n = len(pads)
    while charge < distance:
        while i < n and pads[i][0] <= charge:
            heapq.heappush(reserve, -pads[i][1])
            i += 1
        if not reserve:
            return -1
        charge += -heapq.heappop(reserve)
        halts += 1
    return halts

The obvious version

Track, for each possible number of halts, the farthest milepost the truck could reach using exactly that many halts. Fold the pads in one at a time, updating those numbers backwards, then read off the smallest halt count whose reach clears the corridor.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_fewest_charging_halts(distance, start_charge, pads):
    n = len(pads)
    best = [start_charge] + [-1] * n
    for i in range(n):
        pos, amount = pads[i]
        for used in range(i, -1, -1):
            if best[used] >= pos and best[used] + amount > best[used + 1]:
                best[used + 1] = best[used] + amount
    for used in range(n + 1):
        if best[used] >= distance:
            return used
    return -1

How this problem was checked

Reference solution executed against 18 test cases — 18 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in