We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximize Profit from Task Assignment

Number: 3818

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given an array of workers where each worker’s value represents their skill level, and a list of tasks (each described by a required skill level and an associated profit), assign at most one task to each worker (with the caveat that a worker can only do a task if their skill exactly matches the task’s requirement). In addition, there is one extra worker who can take on any task regardless of its required skill. The goal is to maximize total profit by optimally matching workers to tasks.

Key Insights

  • Regular workers can only perform tasks that exactly match their skill level.
  • For each skill level, assign the most profitable tasks to the available workers having that skill.
  • Any task that is not completed by its matching workers becomes eligible for the extra worker.
  • The extra worker can add at most one additional task to the total profit, so it is optimal to pick the leftover task with the highest profit.
  • Grouping tasks by their required skill and then sorting profits in descending order simplifies the assignment process.

Space and Time Complexity

Time Complexity: O(T log T + W) where T is the number of tasks (grouping and sorting tasks dominates) and W is the number of workers. Space Complexity: O(T + W) for storing the grouped tasks and the worker frequency information.

Solution

To solve the problem, first group tasks by their required skill level and sort each group’s list of profits in descending order. Then, count the number of workers available for each skill level. For every group of tasks, assign as many tasks as possible to the matching workers (always picking the highest profit tasks first). If there are any unassigned tasks in a group (i.e. if there are more tasks than workers for that skill), the task with the highest remaining profit from that group becomes a candidate for the extra worker. Finally, add the profit from the best leftover task (if any) to the total profit computed from the worker assignments.

Key data structures include hash maps (or dictionaries) to store task groups and worker counts, and sorting is used to order tasks by profit. The greedy approach guarantees that we are picking the most profitable available assignments while ensuring that the single extra task by the additional worker maximizes the final reward.

Code Solutions

# Python solution with detailed comments
def maximize_profit(workers, tasks):
    # Import defaultdict to group tasks by their required skill level.
    from collections import defaultdict
    
    # Group tasks by required skill level, mapping each requirement to a list of profits.
    task_groups = defaultdict(list)
    for requirement, profit in tasks:
        task_groups[requirement].append(profit)
    
    # For every group, sort the profits in descending order to assign highest reward tasks first.
    for req in task_groups:
        task_groups[req].sort(reverse=True)
    
    # Count the number of workers available for each skill using a dictionary.
    worker_count = {}
    for skill in workers:
        worker_count[skill] = worker_count.get(skill, 0) + 1
    
    # Initialize total profit from matching workers with tasks.
    total_profit = 0
    # Track the best profit from leftover tasks that were not assigned by matching workers.
    best_leftover_profit = 0
    
    # Iterate over each task group identified by its required skill level.
    for req, profits in task_groups.items():
        # Count how many workers have the exact matching skill.
        available_workers = worker_count.get(req, 0)
        # Determine how many tasks can be assigned - either the number of workers or task count.
        tasks_assigned = min(available_workers, len(profits))
        
        # Sum profit from the assigned tasks.
        total_profit += sum(profits[:tasks_assigned])
        
        # If there are leftover tasks (more tasks than matching workers),
        # update the best candidate for the extra worker with the first unassigned task profit.
        if tasks_assigned < len(profits):
            best_leftover_profit = max(best_leftover_profit, profits[tasks_assigned])
    
    # The additional worker can take one extra task (if available) irrespective of requirements.
    return total_profit + best_leftover_profit

# Example usage:
workers_example = [1, 2, 3, 4, 5]
tasks_example = [[1,100], [2,400], [3,100], [3,400]]
print(maximize_profit(workers_example, tasks_example))  # Expected output: 1000
← Back to All Questions