Show problems as
Classic problem #857HardArrayGreedySortingHeap (Priority Queue)

Minimum Cost to Hire K Workers

Real-world version: Cheapest Crew Under a Fair Rate
Tracked in this browser only
Read Minimum Cost to Hire K Workers on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard 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)

More on the same topics