Maximize profit from task assignment

Array Greedy Sorting Heap (Priority Queue)

65.8% acceptance

Mar 31, 2026

You are given an integer array workers, where workers[i] represents the skill level of the ith worker. You are also given a 2D integer array tasks, where: tasks[i][0] represents the skill requirement needed to complete the task. tasks[i][1] represents the profit earned from completing the task. Each worker can complete at most one task, and they can only take a task if their skill level is equal to the task's skill requirement. An additional worker joins today who can take up any task, regardless of the skill requirement. Return the maximum total profit that can be earned by optimally assigning the tasks to the workers.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn max_profit(workers: Vec<i32>, tasks: Vec<Vec<i32>>) -> i64 {
    // Group tasks by skill requirement, for each skill keep sorted profits
    let mut skill_tasks: HashMap<i32, Vec<i32>> = HashMap::new();
    for t in &tasks {
      skill_tasks.entry(t[0]).or_default().push(t[1]);
    }
    // Sort each group descending by profit
    for v in skill_tasks.values_mut() {
      v.sort_unstable_by(|a, b| b.cmp(a));
    }
    // Count workers per skill
    let mut worker_count: HashMap<i32, usize> = HashMap::new();
    for &w in &workers {
      *worker_count.entry(w).or_default() += 1;
    }
    // Assign workers to matching tasks greedily (highest profit first)
    let mut total: i64 = 0;
    let mut leftover_profits = Vec::new(); // profits from tasks not assigned to matching workers
    
    for (&skill, profits) in &skill_tasks {
      let available = worker_count.get(&skill).copied().unwrap_or(0);
      for (i, &p) in profits.iter().enumerate() {
        if i < available {
          total += p as i64;
        } else {
          leftover_profits.push(p);
        }
      }
    }
    
    // The additional worker can take the highest-profit leftover task
    if let Some(&max_leftover) = leftover_profits.iter().max() {
      total += max_leftover as i64;
    }
    
    total
  }
}