0479EasyArrayMathGreedy

Shunting Pallets Into One Bay

Tracked in this browser only

Trains the technique from

LeetCode 1217Minimum Cost to Move Chips to The Same Position

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.

A loading dock's bays are numbered along a straight line. bays[i] is the bay where pallet i currently sits, and any number of pallets may share a bay.

Pallets are shunted one at a time, and there are two ways to shunt one:

send it two bays along, up or down, and pay nothing, because the shuttle rail is geared for a double hop;
send it one bay along, up or down, and pay 1.

A pallet may be shunted as many times as you like, and it may pass through or stop in any numbered bay, including bays no pallet started in.

Return the smallest total paid to bring every pallet into one common bay.

Examples

Example 1

Input: bays = [3, 5, 8]
Output: 1

Send the pallet in bay 8 down one bay for a charge of 1, then let the shuttle rail carry it down to bay 3 for nothing; the pallet in bay 5 rides the rail to bay 3 free of charge.

Example 2

Input: bays = [4, 4, 4, 7, 7]
Output: 2

The two pallets in bay 7 each pay 1 to reach bay 8, and from there the rail takes them to bay 4 alongside the three already sitting in it.

Example 3

Input: bays = [2, 6, 10]
Output: 0

All three pallets can ride the shuttle rail all the way to bay 2, so nothing is paid.

Constraints

1 <= bays.length <= 100
1 <= bays[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 least_shunt_cost(bays: list[int]) -> int:

Java

public int leastShuntCost(int[] bays)

The intended approach

Time O(n)Space O(1)

A free hop moves a pallet two bays, so it can never change whether the pallet's bay number is even or odd, and a paid hop always does. Tally the pallets sitting in even-numbered bays and the pallets sitting in odd-numbered bays, then return the smaller tally. One pass over the list and two counters are enough.

Pythonentry point: least_shunt_cost

def least_shunt_cost(bays):
    # time O(n), space O(1)
    on_even = 0
    for bay in bays:
        if bay % 2 == 0:
            on_even += 1
    rest = len(bays) - on_even
    return on_even if on_even < rest else rest

The obvious version

Consider every bay from two below the lowest occupied bay to two above the highest as a possible meeting bay. For each one, work out the cheapest way to bring a single pallet from every bay in that window by relaxing hops of size one and two across the window until nothing improves, then add up the charges for the pallets actually on the dock. Keep the smallest total.

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

from collections import deque


def bf_least_shunt_cost(bays):
    low = min(bays) - 2
    high = max(bays) + 2
    span = high - low + 1
    far = 10 ** 9
    cheapest = None
    for target in range(low, high + 1):
        cost = [far] * span
        cost[target - low] = 0
        pending = deque([target - low])
        while pending:
            at = pending.popleft()
            for jump in (-2, 2):
                nxt = at + jump
                if 0 <= nxt < span and cost[nxt] > cost[at]:
                    cost[nxt] = cost[at]
                    pending.append(nxt)
            for jump in (-1, 1):
                nxt = at + jump
                if 0 <= nxt < span and cost[nxt] > cost[at] + 1:
                    cost[nxt] = cost[at] + 1
                    pending.append(nxt)
        total = 0
        for bay in bays:
            total += cost[bay - low]
        if cheapest is None or total < cheapest:
            cheapest = total
    return cheapest

How this problem was checked

Reference solution executed against 9 test cases — 9 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