1143HardArrayDynamic ProgrammingBacktrackingBit ManipulationBitmask

Handing Out Runs to Keep the Longest Shift Short

Tracked in this browser only

Trains the technique from

LeetCode 1723Find Minimum Time to Finish All Jobs

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 depot has runs to hand out, and runs[i] is how long run i takes. Every run goes to exactly one of k drivers, and a driver's shift is the total time of the runs handed to them. A driver may end up with no runs at all.

Hand out every run so that the longest shift is as short as it can be, and return that length.

Examples

Example 1

Input: runs = [3, 3, 2, 2, 2], k = 2
Output: 6

Giving one driver the two runs of 3 and the other the three runs of 2 makes both shifts 6, and since the whole total is 12 no shorter longest shift is possible.

Example 2

Input: runs = [5, 5], k = 2
Output: 5

One run each, so both shifts come to 5.

Example 3

Input: runs = [10, 1, 1], k = 2
Output: 10

Some driver has to take the run of 10 whatever else happens, so the longest shift is at least that, and the other driver can take both short runs.

Constraints

1 <= k <= runs.length <= 12
1 <= runs[i] <= 10^7

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 minimum_time_required(runs: list[int], k: int) -> int:

Java

public int minimumTimeRequired(int[] runs, int k)

The intended approach

Time O(k^n log(total)) in the worst case, though the prunings cut it hard.Space O(n + k) for the ordered runs and the shifts.

Whether a given length is good enough is easier to answer than what the best length is: if every run can be packed into `k` shifts none longer than a cap, then any larger cap works too. So the answer is the smallest workable cap and can be hunted down by halving the range between the longest single run, which no cap can beat, and the total of all runs, which one driver alone could take. Testing a cap means trying to pack the runs. Take them longest first and hand each to some driver whose shift still has room, backing out when the packing gets stuck. Longest first matters because a long run left to the end has the fewest places it could go, so its failure is discovered late. Two prunings make the packing bearable. A driver whose shift is already too full for the run in hand is skipped, and two drivers whose shifts currently total the same are interchangeable, so only the first of them is tried. Without that second pruning the same packing would be re-examined once per way of naming the drivers.

Pythonentry point: minimum_time_required

def minimum_time_required(runs, k):
    order = sorted(runs)
    order.reverse()
    n = len(order)
    load = [0] * k

    def place(i, cap):
        if i == n:
            return True
        tried = set()
        for d in range(k):
            if load[d] in tried:
                continue
            if load[d] + order[i] > cap:
                continue
            tried.add(load[d])
            load[d] += order[i]
            if place(i + 1, cap):
                return True
            load[d] -= order[i]
        return False

    lo = order[0]
    hi = 0
    for value in order:
        hi += value
    while lo < hi:
        mid = (lo + hi) // 2
        for d in range(k):
            load[d] = 0
        if place(0, mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

The obvious version

Work out the total of every set of runs, then build up the answer one driver at a time: for one driver a set costs its whole total, and for one more driver the cost of a set is the best over every way of splitting off what that driver takes, paying the larger of that driver's total and what the others manage with the rest. Costs three to the power of the run count for each driver.

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_minimum_time_required(runs, k):
    n = len(runs)
    full = (1 << n) - 1
    total = [0] * (1 << n)
    for mask in range(1, 1 << n):
        low = mask & (-mask)
        i = low.bit_length() - 1
        total[mask] = total[mask ^ low] + runs[i]
    big = 1 << 60
    best = list(total)
    for _ in range(1, k):
        step = [big] * (1 << n)
        for mask in range(1 << n):
            sub = mask
            while True:
                worst = best[mask ^ sub]
                if total[sub] > worst:
                    worst = total[sub]
                if worst < step[mask]:
                    step[mask] = worst
                if sub == 0:
                    break
                sub = (sub - 1) & mask
        best = step
    return best[full]

How this problem was checked

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