LeetCode Solutions
826. Most Profit Assigning Work
Time: $O(n\log n + k\log k)$, where $n = |\texttt{jobs}|$ and $k = |\texttt{worker}|$ Space: $O(n)$
class Solution {
public:
int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit,
vector<int>& worker) {
int ans = 0;
vector<pair<int, int>> jobs;
for (int i = 0; i < difficulty.size(); ++i)
jobs.emplace_back(difficulty[i], profit[i]);
sort(begin(jobs), end(jobs));
sort(begin(worker), end(worker));
int i = 0;
int maxProfit = 0;
for (const int w : worker) {
for (; i < jobs.size() && w >= jobs[i].first; ++i)
maxProfit = max(maxProfit, jobs[i].second);
ans += maxProfit;
}
return ans;
}
};
class Solution {
public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
int ans = 0;
List<Pair<Integer, Integer>> jobs = new ArrayList<>();
for (int i = 0; i < difficulty.length; ++i)
jobs.add(new Pair<>(difficulty[i], profit[i]));
Collections.sort(jobs, Comparator.comparing(Pair::getKey));
Arrays.sort(worker);
int i = 0;
int maxProfit = 0;
for (final int w : worker) {
for (; i < jobs.size() && w >= jobs.get(i).getKey(); ++i)
maxProfit = Math.max(maxProfit, jobs.get(i).getValue());
ans += maxProfit;
}
return ans;
}
}
class Solution:
def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
ans = 0
jobs = sorted(zip(difficulty, profit))
worker.sort(reverse=1)
i = 0
maxProfit = 0
for w in sorted(worker):
while i < len(jobs) and w >= jobs[i][0]:
maxProfit = max(maxProfit, jobs[i][1])
i += 1
ans += maxProfit
return ans