Solution: Minimum Cost to Hire K Workers

Statement▼

You are given $n$ workers, each characterized by two attributes:

You want to hire exactly k workers to form a paid group, and you must follow these payment rules:

Wage expectation: Every worker in the group must be paid at least their minimum wage expectation.
Proportional pay: The pay for each worker must be directly proportional to their quality. For example, if one worker’s quality is twice that of another, they must be paid twice as much.

Your goal is to determine the least amount of money required to hire exactly k workers while satisfying the above conditions.

Constraints

⋮

Tap here to switch tabs

Problem

Ask

Submissions

Solution

You are given $n$ workers, each characterized by two attributes:

You want to hire exactly k workers to form a paid group, and you must follow these payment rules:

Wage expectation: Every worker in the group must be paid at least their minimum wage expectation.
Proportional pay: The pay for each worker must be directly proportional to their quality. For example, if one worker’s quality is twice that of another, they must be paid twice as much.

Your goal is to determine the least amount of money required to hire exactly k workers while satisfying the above conditions.

Constraints