0725MediumArrayBinary SearchGreedy

Evening Out The Van Loads

Tracked in this browser only

Trains the technique from

LeetCode 2064Minimized Maximum of Products Distributed to Any Store

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 sorting hub has couriers vans on the yard tonight and a depot list loads, where loads[i] is the number of parcels waiting at depot i.

Every parcel has to be moved. A van is sent to at most one depot, so everything it carries comes from that single depot, and a van may also be left on the yard carrying nothing. The parcels of a depot may be split between the vans sent to it in any whole numbers you like.

Plan the run so that the heaviest van load is as small as it can be, and return that load.

Examples

Example 1

Input: couriers = 6, loads = [11, 6]
Output: 3

Send four vans to the first depot carrying 3, 3, 3 and 2 parcels, and two vans to the second carrying 3 each. That is six vans, every parcel is moved, and no van carries more than 3.

Example 2

Input: couriers = 3, loads = [10, 1, 1]
Output: 10

The two single-parcel depots each need a van of their own, which leaves one van for the depot holding 10, and that van has to take all 10.

Example 3

Input: couriers = 4, loads = [6, 2]
Output: 2

Three vans take 2 parcels each from the first depot and the fourth van takes both parcels of the second depot, so the heaviest van carries 2.

Constraints

1 <= loads.length <= couriers <= 10^5
1 <= loads[i] <= 10^5

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 min_largest_van_load(couriers: int, loads: list[int]) -> int:

Java

public int minLargestVanLoad(int couriers, int[] loads)

The intended approach

Time O(m log(max load)) for m depots.Space O(1)

Ask instead whether a given cap on a single van's load can be met. Under a cap of `c`, depot `i` needs its parcel count divided by `c` and rounded up, and the plan works when those counts add up to no more than the fleet size. A cap that works stays working when it is raised, so the workable caps form the upper part of the range from 1 to the largest depot, and the smallest of them is found by repeatedly halving that range.

Pythonentry point: min_largest_van_load

def min_largest_van_load(couriers, loads):
    # A cap on how much one van may carry is workable when the vans it forces,
    # summed over the depots, fit inside the fleet.  Raising the cap never needs
    # more vans, so the workable caps form an upper stretch and can be found by
    # halving the range between 1 and the biggest depot.
    # Time O(m log(max load)) for m depots.  Space O(1).
    def fits(cap):
        vans = 0
        for parcels in loads:
            vans += (parcels + cap - 1) // cap
            if vans > couriers:
                return False
        return True

    low = 1
    high = max(loads)
    while low < high:
        mid = (low + high) // 2
        if fits(mid):
            high = mid
        else:
            low = mid + 1
    return low

The obvious version

Try every cap starting at 1 and climbing by one. For each cap, add up the vans the depots need when their parcels are cut into groups no bigger than the cap, and return the first cap the fleet can cover.

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_min_largest_van_load(couriers, loads):
    cap = 1
    while True:
        vans = 0
        for parcels in loads:
            whole = parcels // cap
            if parcels % cap:
                whole += 1
            vans += whole
        if vans <= couriers:
            return cap
        cap += 1

How this problem was checked

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