Skip to content

3476. Maximize Profit from Task Assignment 👍

  • Time: $O(\texttt{sort}(\texttt{tasks}) + |\texttt{workers}|)$
  • Space: $O(|\texttt{tasks}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
 public:
  long long maxProfit(vector<int>& workers, vector<vector<int>>& tasks) {
    long totalProfit = 0;
    int maxRemainingProfit = 0;
    unordered_map<int, vector<int>> skillToProfits;

    for (const vector<int>& task : tasks) {
      const int skill = task[0];
      const int profit = task[1];
      skillToProfits[skill].push_back(profit);
    }

    for (auto& [_, profits] : skillToProfits)
      ranges::sort(profits, greater<int>());

    for (const int workerSkill : workers)
      if (skillToProfits.contains(workerSkill) &&
          !skillToProfits[workerSkill].empty()) {
        const int profit = skillToProfits[workerSkill][0];
        skillToProfits[workerSkill].erase(skillToProfits[workerSkill].begin());
        totalProfit += profit;
      }

    for (const auto& [_, profits] : skillToProfits)
      if (!profits.empty())
        maxRemainingProfit = max(maxRemainingProfit, profits[0]);

    return totalProfit + maxRemainingProfit;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  public long maxProfit(int[] workers, int[][] tasks) {
    long totalProfit = 0;
    int maxRemainingProfit = 0;
    Map<Integer, List<Integer>> skillToProfits = new HashMap<>();

    for (int[] task : tasks) {
      final int skill = task[0];
      final int profit = task[1];
      skillToProfits.computeIfAbsent(skill, k -> new ArrayList<>()).add(profit);
    }

    for (List<Integer> profits : skillToProfits.values())
      Collections.sort(profits, Collections.reverseOrder());

    for (final int workerSkill : workers)
      if (skillToProfits.containsKey(workerSkill) && !skillToProfits.get(workerSkill).isEmpty()) {
        final int profit = skillToProfits.get(workerSkill).get(0);
        skillToProfits.get(workerSkill).remove(0);
        totalProfit += profit;
      }

    for (List<Integer> profits : skillToProfits.values())
      if (!profits.isEmpty())
        maxRemainingProfit = Math.max(maxRemainingProfit, profits.get(0));

    return totalProfit + maxRemainingProfit;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def maxProfit(self, workers: list[int], tasks: list[list[int]]) -> int:
    totalProfit = 0
    skillToProfits = collections.defaultdict(list)

    for skill, profit in tasks:
      skillToProfits[skill].append(profit)

    for skill in skillToProfits:
      skillToProfits[skill].sort(reverse=True)

    for workerSkill in workers:
      if workerSkill in skillToProfits and skillToProfits[workerSkill]:
        profit = skillToProfits[workerSkill][0]
        skillToProfits[workerSkill].pop(0)
        totalProfit += profit

    return totalProfit + max(max(profits, default=0)
                             for profits in skillToProfits.values())