Sponsored
Sponsored
In this approach, we sort both jobs by difficulty and workers by their ability. We then iterate over each worker and find the highest profit job they can perform using a greedy approach.
First, we pair each job's difficulty with its profit and then sort these pairs by difficulty. We also sort the worker array. Next, for each worker, we iterate through the sorted job list and keep track of the maximum profit the worker can obtain, given that their ability must be greater than or equal to the job's difficulty. This ensures that each worker is assigned the most profitable job they can perform, thus maximizing the total profit.
Time Complexity: O(n log n + m log m)
Space Complexity: O(n)
1#include <stdio.h>
2#include <stdlib.h>
3
4int compareJobs(const void *a, const void *b) {
5 return ((int *)a)[0] - ((int *)b)[0];
6}
7
8int compareWorkers(const void *a, const void *b) {
9 return (*(int *)a) - (*(int *)b);
10}
11
12int maxProfitAssignment(int* difficulty, int difficultySize, int* profit, int profitSize, int* worker, int workerSize) {
13 int jobs[difficultySize][2];
14 for (int i = 0; i < difficultySize; i++) {
15 jobs[i][0] = difficulty[i];
16 jobs[i][1] = profit[i];
17 }
18 qsort(jobs, difficultySize, sizeof(jobs[0]), compareJobs);
19 qsort(worker, workerSize, sizeof(int), compareWorkers);
20
21 int maxProfit = 0, best = 0, j = 0;
22 for (int i = 0; i < workerSize; i++) {
23 while (j < difficultySize && worker[i] >= jobs[j][0]) {
24 best = (best > jobs[j][1]) ? best : jobs[j][1];
25 j++;
26 }
27 maxProfit += best;
28 }
29 return maxProfit;
30}
31
32int main() {
33 int difficulty[] = {2, 4, 6, 8, 10};
34 int profit[] = {10, 20, 30, 40, 50};
35 int worker[] = {4, 5, 6, 7};
36 int maxProfit = maxProfitAssignment(difficulty, 5, profit, 5, worker, 4);
37 printf("Max Profit: %d\n", maxProfit);
38 return 0;
39}The solution first sorts the jobs based on their difficulty and profits, and then sorts the workers based on their ability. It uses a while loop to traverse through eligible jobs for each worker and tracks the maximum profit they can make, which is then added to the total profit.
This approach improves efficiency by preparing the job list in advance for profit maximization, and processes each worker in one pass. The basic idea is to preprocess the jobs to track the maximum profit obtainable up to each difficulty level. We create a running maximum profit and apply this to each worker based on their ability directly.
First, jobs are paired and sorted by difficulty; then, as we iterate through them, we constantly update the maximum profit obtainable up to each job's difficulty. When assessing workers, we simply apply their ability to this precomputed list to find the applicable maximum profit, ensuring minimal lookups and passing through the sorted jobs just once.
Time Complexity: O(n log n + m log m)
Space Complexity: O(n)
#include <vector>
#include <algorithm>
using namespace std;
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
vector<pair<int, int>> jobs;
for (size_t i = 0; i < difficulty.size(); ++i) {
jobs.emplace_back(difficulty[i], profit[i]);
}
sort(jobs.begin(), jobs.end());
sort(worker.begin(), worker.end());
int maxProfit = 0, best = 0, j = 0;
for (auto& job : jobs) {
best = max(best, job.second);
job.second = best; // Update the job profit to maximum up to this difficulty
}
for (auto& ability : worker) {
while (j < jobs.size() && ability >= jobs[j].first) {
++j;
}
if (j > 0) {
maxProfit += jobs[j - 1].second;
}
}
return maxProfit;
}
int main() {
vector<int> difficulty = {2, 4, 6, 8, 10};
vector<int> profit = {10, 20, 30, 40, 50};
vector<int> worker = {4, 5, 6, 7};
int maxProfit = maxProfitAssignment(difficulty, profit, worker);
cout << "Max Profit: " << maxProfit << endl;
return 0;
}This C++ solution preprocesses jobs to store the max profit obtainable by each difficulty level. It iterates through the workers only once, applying precomputed profits for quick total calculation.