LeetCode 3476 - Maximize Profit from Task Assignment

This problem asks us to assign tasks to workers in order to maximize total profit, under strict skill constraints. Each worker has a skill level, and each task has a required skill and an associated profit.

leetcodemediumarraygreedysortingheap-(priority-queue)

LeetCode Problem 3476

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting, Heap (Priority Queue)

Solution

Problem Understanding

This problem asks us to assign tasks to workers in order to maximize total profit, under strict skill constraints. Each worker has a skill level, and each task has a required skill and an associated profit. A worker can only complete a task if their skill exactly matches the task's required skill. Additionally, there is one extra "flexible" worker who can complete any task regardless of skill. Each worker, including the flexible one, can perform at most one task.

The input consists of an array of workers’ skill levels and a list of tasks where each task is represented as a pair [required_skill, profit]. The output is a single integer, the maximum sum of profits achievable by optimally assigning tasks.

The constraints indicate that both workers and tasks can be as large as 100,000, and skill/profit values can go up to 10^9. This implies that any solution with nested loops over workers and tasks (O(n*m)) will be too slow. We need an approach that efficiently matches tasks to workers.

Important edge cases include:

  • No worker matches a task’s skill requirement.
  • Multiple tasks with the same skill requirement.
  • Only one worker or one task.
  • The flexible worker may be the only one able to do some tasks.

Approaches

Brute Force

A naive brute-force solution would attempt all permutations of assigning tasks to workers while respecting skill requirements. This ensures correctness because we consider every possible allocation. After evaluating all combinations, we could pick the one that yields the maximum profit. However, this approach is impractical because the number of combinations grows factorially with the number of tasks or workers, making it infeasible for n, m ≈ 10^5.

Optimal Approach

The key insight is that the flexible worker allows us to always pick the most profitable remaining task after matching exact-skill workers. Therefore, we can separate the problem into two parts: matching tasks to exact-skill workers and then assigning the remaining highest-profit task to the flexible worker.

We can solve this efficiently by grouping tasks by skill requirement and sorting them in descending order of profit. For each worker, we pick the highest-profit task they qualify for. After assigning tasks to all exact-match workers, the flexible worker can take the remaining highest-profit task. Using a max-heap or sorting by profit allows us to efficiently select the best available task at each step.

This approach reduces the complexity significantly because we avoid considering all permutations and instead focus on efficient sorting and selection.

Approach Time Complexity Space Complexity Notes
Brute Force O(m!) O(m) Tries all assignments; infeasible for large input
Optimal O(n log n + m log m) O(m) Sort workers and tasks, use hash map + heap to assign tasks efficiently

Algorithm Walkthrough

  1. Group tasks by skill: Use a dictionary mapping each required skill to a max-heap of task profits. This allows efficient retrieval of the most profitable task for each skill.
  2. Sort workers: Sorting workers helps iterate over them deterministically. This is not strictly required for correctness, but it simplifies processing.
  3. Assign tasks to exact-skill workers: For each worker, check if there are tasks matching their skill. If so, pop the highest-profit task from the corresponding heap and add it to the total profit.
  4. Collect remaining tasks: After assigning all exact-skill workers, push the remaining unassigned task profits into a max-heap.
  5. Assign the flexible worker: Pop the highest-profit task from the remaining heap and add it to the total profit. This ensures the flexible worker contributes maximally.

Why it works: The invariant is that each worker takes the highest-profit task they are eligible for, and the flexible worker takes the single remaining most profitable task. This greedy approach guarantees maximum total profit because no profitable task is skipped when it could be assigned.

Python Solution

from typing import List
import heapq
from collections import defaultdict

class Solution:
    def maxProfit(self, workers: List[int], tasks: List[List[int]]) -> int:
        # Group tasks by skill with max-heaps of profits
        task_map = defaultdict(list)
        for skill, profit in tasks:
            heapq.heappush(task_map[skill], -profit)
        
        total_profit = 0
        remaining_profits = []

        # Assign tasks to exact-skill workers
        for worker in workers:
            if task_map[worker]:
                total_profit += -heapq.heappop(task_map[worker])
        
        # Collect all remaining tasks for the flexible worker
        for profits in task_map.values():
            while profits:
                heapq.heappush(remaining_profits, -heapq.heappop(profits))
        
        # Assign the flexible worker the most profitable remaining task
        if remaining_profits:
            total_profit += -heapq.heappop(remaining_profits)
        
        return total_profit

This implementation first constructs a mapping from skill to tasks using a max-heap for efficient retrieval of the most profitable tasks. Workers are processed to take their matching task if available. Finally, all leftover tasks are considered for the flexible worker, who takes the most profitable one.

Go Solution

package main

import (
    "container/heap"
    "sort"
)

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any)        { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func maxProfit(workers []int, tasks [][]int) int64 {
    taskMap := make(map[int]*IntHeap)
    for _, task := range tasks {
        skill, profit := task[0], task[1]
        if _, ok := taskMap[skill]; !ok {
            taskMap[skill] = &IntHeap{}
        }
        heap.Push(taskMap[skill], profit)
    }

    var total int64 = 0
    remaining := &IntHeap{}
    heap.Init(remaining)

    for _, worker := range workers {
        if h, ok := taskMap[worker]; ok && h.Len() > 0 {
            total += int64(heap.Pop(h).(int))
        }
    }

    for _, h := range taskMap {
        for h.Len() > 0 {
            heap.Push(remaining, heap.Pop(h).(int))
        }
    }

    if remaining.Len() > 0 {
        total += int64(heap.Pop(remaining).(int))
    }

    return total
}

The Go version mirrors the Python approach. A max-heap is implemented using the container/heap interface. Tasks are assigned to exact-skill workers first, and the flexible worker then takes the largest remaining task.

Worked Examples

Example 1

Workers: [1,2,3,4,5]

Tasks: [[1,100],[2,400],[3,100],[3,400]]

  1. Group tasks:

{1:[100],2:[400],3:[400,100]} 2. Assign exact-skill workers:

Worker 1 → 100, Worker 2 → 400, Worker 3 → 400 3. Remaining tasks: [100] 4. Flexible worker → 100

Total profit = 100 + 400 + 400 + 100 = 1000

Example 2

Workers: [10,10000,100000000]

Tasks: [[1,100]]

No workers match the skill requirement. Flexible worker → 100

Total profit = 100

Example 3

Workers: [7]

Tasks: [[3,3],[3,3]]

Worker cannot do any task. Flexible worker → 3

Total profit = 3

Complexity Analysis

Measure Complexity Explanation
Time O(n log n + m log m) Sorting tasks and using heaps dominates, where n = workers.length, m = tasks.length
Space O(m) We store all tasks in heaps for assignment

Sorting and heap operations allow us to efficiently select the best task for each worker without iterating over all possibilities, which would be infeasible for large inputs.

Test Cases

# Provided examples
assert Solution().maxProfit([1,2,3,4,5], [[1,100],[2,400],[3,100],[3,400]]) == 1000  # example 1
assert Solution().maxProfit([10,10000,100000000], [[1,100]]) == 100  # example 2
assert Solution().maxProfit([7], [[3,3],[3,3]]) == 3  # example 3

# Edge cases
assert Solution().maxProfit([1], [[1,50]]) == 50  # single worker, single matching task
assert Solution().maxProfit([1], [[2,50]]) == 50  # single worker, task requires different skill, flexible worker picks
assert Solution().maxProfit([], [[5,100]]) ==