0871HardArrayGreedySortingHeap (Priority Queue)

Cheapest Crew Under a Fair Rate

Tracked in this browser only

Trains the technique from

LeetCode 857Minimum Cost to Hire K Workers

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 may hire from n fitters. Fitter i works at output output[i] and will not work below a pay floor of floor[i].

Exactly k fitters are hired, and the depot must pay in proportion to output: if two hired fitters have outputs a and b, their pay must be in the ratio a to b. Every hired fitter must also be paid at least their own floor.

Return the least total pay that hires k fitters. An answer within 1e-5 of the true value is accepted.

Examples

Example 1

Input: output = [10, 20, 5], floor = [70, 50, 30], k = 2
Output: 105.0

Hiring the second and third fitters means a rate of at least 6 per unit of output, since the third demands 30 for an output of 5, and their outputs of 20 and 5 come to 25, for a total pay of 150.

Example 2

Input: output = [4], floor = [8], k = 1
Output: 8.0

The only fitter must be hired and demands 8, which is a rate of 2 per unit of output.

Example 3

Input: output = [2, 4, 6, 8], floor = [1, 1, 1, 1], k = 4
Output: 10.0

All four must be hired. The fitter with output 2 demands the highest rate, half a unit of pay per unit of output, and the outputs come to 20.

Constraints

1 <= output.length <= 10^4
output.length == floor.length
1 <= k <= 10000
k is at most output.length
1 <= output[i] <= 10^4
1 <= floor[i] <= 10^4

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 cheapest_crew(output: list[int], floor: list[int], k: int) -> float:

Java

public double cheapestCrew(int[] output, int[] floor, int k)

The intended approach

Time O(n log n) for n fitters: one sort and one heap pass.Space O(n) for the sorted ratios and the heap.

Paying in proportion to output means there is a single rate per unit of output, and the rate has to be at least each hired fitter's floor divided by their own output. So the rate is set by whichever hired fitter has the largest such ratio, and the total pay is that rate times the outputs added together. Sort the fitters by their ratio and walk them: with the current fitter setting the rate, the cheapest crew takes the `k - 1` smallest outputs among those already seen, which a running total over a heap of the largest kept outputs supplies. Keeping the total of the `k` smallest outputs seen so far and multiplying by the current ratio gives a candidate, and the smallest candidate is the answer.

Pythonentry point: cheapest_crew

def cheapest_crew(output, floor, k):
    import heapq
    order = sorted(range(len(output)), key=lambda i: floor[i] / output[i])
    kept = []          # a max-heap of the outputs currently kept, negated
    total = 0
    best = None
    for i in order:
        heapq.heappush(kept, -output[i])
        total += output[i]
        if len(kept) > k:
            total += heapq.heappop(kept)
        if len(kept) == k:
            cost = total * floor[i] / output[i]
            if best is None or cost < best:
                best = cost
    return float(best)

The obvious version

Try every set of `k` fitters, work out the rate that set forces as the largest floor divided by output among them, and total the pay. Keeps the cheapest. Exponential in the fitter count, but it never reasons about which outputs to keep.

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_cheapest_crew(output, floor, k):
    import itertools
    n = len(output)
    best = None
    for combo in itertools.combinations(range(n), k):
        rate = 0.0
        for i in combo:
            r = floor[i] / output[i]
            if r > rate:
                rate = r
        total = 0
        for i in combo:
            total += output[i]
        cost = total * rate
        if best is None or cost < best:
            best = cost
    return float(best)

How this problem was checked

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