Problem

Example 1:

Solution

Method 1 – Greedy with Sorting and Two Pointers

Intuition

To maximize profit, assign the most profitable tasks to the most skilled workers. Sort both arrays and pair the largest profits with the largest skills.

Approach

  1. Sort the profit array in descending order.
  2. Sort the worker array in descending order.
  3. Assign the highest profit task to the highest skill worker, the next highest to the next, and so on, until one of the arrays is exhausted.
  4. Sum the assigned profits.
  5. Return the total profit.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    int maxProfitAssignment(vector<int>& profit, vector<int>& worker) {
        sort(profit.rbegin(), profit.rend());
        sort(worker.rbegin(), worker.rend());
        int n = min(profit.size(), worker.size()), ans = 0;
        for (int i = 0; i < n; ++i) ans += profit[i] * worker[i];
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int maxProfitAssignment(int[] profit, int[] worker) {
        Arrays.sort(profit);
        Arrays.sort(worker);
        int n = Math.min(profit.length, worker.length), ans = 0;
        for (int i = 0; i < n; i++) {
            ans += profit[profit.length-1-i] * worker[worker.length-1-i];
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def maxProfitAssignment(self, profit: list[int], worker: list[int]) -> int:
        profit.sort(reverse=True)
        worker.sort(reverse=True)
        ans = 0
        for p, w in zip(profit, worker):
            ans += p * w
        return ans

Complexity

  • ⏰ Time complexity: O(n log n) — for sorting both arrays.
  • 🧺 Space complexity: O(1) — extra space for variables only.