Each worker ~k~ is described by two numbers: his minimum salary ~S_k~ and his qualification ~Q_k~.

Imagine that we already picked a set ~K~ of workers we want to hire. How do we compute the total amount of money we need to pay them?

According to the problem statement, the salaries must be proportional to the qualification levels. Hence, there must be some unit salary ~u~ such that each employee ~k \in K~ will be paid ~u Q_k~ dollars. However, each employee's salary must be at least as large as his minimum salary. Therefore, ~u~ must be large enough to guarantee that for each ~k \in K~ we have ~u Q_k \ge S_k~.

For more clarity, we can rewrite the last condition as follows: For each ~k \in K~ we must have ~u \ge S_k/Q_k~. Let us label ~S_k/Q_k~ as ~U_k~ — the minimum unit cost at which worker ~k~ can be employed. We also want to pay as little as possible, hence we want to pick the smallest ~u~ that satisfies all the conditions. Therefore we get:

$$\displaystyle u = \max_{k \in K} U_k$$

Note that this means that the unit salary is determined by a single employee in ~K~ — the one with the largest value of ~U_k~.

We just showed that for any set of workers ~K~ (therefore also for the optimal set) the unit salary ~u~ is equal to the value ~U_k~ of one of the workers in ~K~. This means that there are only ~\mathcal O(N)~ possible values of ~u~.

Now imagine that we start constructing the optimal set of workers ~K~ by picking the unit salary ~u~. Once we pick ~u~, we know that we may hire only those workers ~k~ for which ~U_k \le u~. But how do we determine which of them to hire?

This is easy: if we hire a worker with qualification ~Q_k~, we will have to pay him ~u Q_k~ dollars. In order to maximize the number of workers we can afford (and minimize the cost at which we do so), we clearly want to hire the least-qualified workers.

Hence, we can compute the best solution for a given unit cost ~u~ by finding all the workers that we may hire, ordering them by qualification, and then greedily picking them one by one (starting from the least qualified) while we can still afford to pay them.

This gives us an ~\mathcal O(N^2 \log N)~ solution. The solution can easily be improved to ~\mathcal O(N^2)~, as we can sort the workers according to their qualification once in the beginning, and then each possible unit cost ~u~ can be tried in ~\mathcal O(N)~.

Finally, we'll show how to improve the above algorithm to ~\mathcal O(N \log N)~. We'll start by ordering all workers according to the value ~U_k~ in ascending order, and we label the workers ~k_1, k_2, \dots, k_N~ in this order.

In order to find the optimum set of workers, we'll do exactly the same as in the previous algorithm, only in a more efficient way.

Let ~Z(m)~ be the following question: "What is the optimal subset of ~\{k_1, \dots, k_m\}~, given that the unit salary is ~U_{k_m} = S_{k_m}/Q_{k_m}~?"

From the discussion above it follows that the optimal solution has to be the answer to a question ~Z(m)~ for some ~m~. Hence all we need to do is to answer these ~N~ questions.

The inefficient part of the previous solution lies in the fact that for each ~m~ we were doing the computation all over again. We can now note that we do not have to do this — we may compute the answer to ~Z(m+1)~ from the answer to ~Z(m)~, for each ~m~.

Assume that we already know the optimal answer to ~Z(m)~ for some ~m~. We will store the workers we picked in a priority queue ~Q~ ordered according to their qualification, with more qualified workers having higher priority.

Now we want to add the worker ~k_{m+1}~. His qualification level may make him a better candidate than some of the workers we have already processed. We add him into the priority queue ~Q~. ~Q~ now contains all workers we need to consider when looking for the current optimal solution, because if a worker had a qualification too large to be in the optimal solution for ~m~, we will never want to use him again. This holds because the unit cost never decreases and the pool of workers only grows, so the cost of employing a worker together with all available less-qualified workers will only go up.

However, ~Q~ may still differ from the optimal answer to ~Z(k+1)~, because the cost of paying all the workers in ~Q~ might exceed the budget ~W~. There are two reasons for this: first, when adding the worker ~k_{m+1}~ the current unit salary ~u~ may have increased. And second, even if it stayed the same, we added another worker, and this alone could make the total salary of the chosen workers greater than ~W~.

Hence, we now may need to adjust the set of chosen workers by repeatedly throwing away the most qualified one, until we can afford to pay them all. And this is where the priority queue comes in handy.

To summarize, the 100-point solution we just derived looks as follows: first, order the workers according to the unit salary they enforce. Then, process the workers in the order computed in step 1. Keep the currently optimal set of workers in a priority queue ~Q~, and keep an additional variable ~T~ equal to the sum of qualifications of all workers in ~Q~. For each worker ~k~, we first add him into ~Q~ (and update ~T~ accordingly), and then we throw away the largest elements of ~Q~ while we cannot afford to pay them all — that is, while ~T S_{k_m}/Q_{k_m}~ exceeds the amount of money we have.

Once we are finished, we know the numeric parameters of the optimal solution – the optimal number of workers, the minimum cost to hire that many workers, and the number ~f~ of the worker for which we found it. To actually construct the solution, it is easiest to start the process once again from the beginning, and stop after processing ~f~ workers.

The first step (sorting) can be done in ~\mathcal O(N \log N)~.

In the second step (finding the optimal number of workers and the cost of hiring them), for each worker we insert his qualification into ~Q~ once, and we remove it from ~Q~ at most once. Hence there are at most ~2N~ operations with the priority queue, and each of those can be done in ~\mathcal O(\log N)~ (e.g., if the priority queue is implemented as a binary heap).

The third step (constructing one optimal set of workers) takes at most as long as the second step.

Therefore the total time complexity of this solution is ~\mathcal O(N \log N)~.

Alternative solution Instead of iterating ~m~ upwards, it is also possible to iterate it downwards. Suppose that ~P~ is the optimal subset of ~\{k_1, \dots, k_m\}~ with ~u = U_{k_m}~, and we wish to modify ~P~ to find the optimal subset of ~\{k_1, \dots, k_{m-1}\}~ with ~u = U_{k_{m-1}}~. Firstly, we must remove ~k_m~ from ~Q~ if it is currently present. By potentially having reduced ~u~ and/or removed a worker, we may have freed up more money to hire workers. But which workers should we hire?

Clearly, we cannot hire any workers that we are already employing. Also, the only reason we ever remove a worker ~k~ from ~P~ is because ~u~ fell below ~U_k~, and since ~u~ only decreases that worker can never be hired again. Hence, we can maintain a simple queue of workers, ordered by qualification, and just hire the next available worker until there is not enough money to do so. It is also necessary to remove workers from this queue when ~u~ decreases, but this can be achieved by flagging workers as unemployable and skipping over them.

Each worker can be added to the optimal set at most once, and removed from the optimal set at most once. Each of these steps requires only constant time, so the core of this algorithm requires ~\mathcal O(N)~ time. However, the initial sorting still requires ~\mathcal O(N \log N)~ time.