Maximize Profit from Task Assignment - Practice Coding Problems

Maximize Profit from Task Assignment - Problem

You are given an integer array workers, where workers[i] represents the skill level of the i-th 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.

Input & Output

Example 1 — Basic Assignment

$ Input: workers = [3,1,2], tasks = [[1,7],[2,4],[3,5]]

› Output: 16

💡 Note: Worker with skill 1 takes task [1,7] for profit 7, worker with skill 2 takes task [2,4] for profit 4, worker with skill 3 takes task [3,5] for profit 5. Total profit = 7 + 4 + 5 = 16

Example 2 — Super Worker Needed

$ Input: workers = [1,1], tasks = [[1,5],[2,6],[1,3]]

› Output: 14

💡 Note: Two workers with skill 1 can take tasks [1,5] and [1,3] for profit 5+3=8. Super worker takes remaining task [2,6] for profit 6. Total = 8 + 6 = 14

Example 3 — More Tasks Than Workers

$ Input: workers = [2], tasks = [[1,8],[2,7],[3,6]]

› Output: 15

💡 Note: Regular worker with skill 2 takes task [2,7] for profit 7. Super worker takes highest remaining task [1,8] for profit 8. Total = 7 + 8 = 15

Constraints

1 ≤ workers.length ≤ 10⁵
1 ≤ tasks.length ≤ 10⁵
1 ≤ workers[i], tasks[i][0] ≤ 10⁵
1 ≤ tasks[i][1] ≤ 10⁸

Visualization

Tap to expand

Understanding the Visualization

Input

Workers with skill levels and tasks with skill requirements and profits

Process

Match workers to tasks optimally, using super worker for any unmatched task

Output

Maximum total profit achievable

Key Takeaway

🎯 Key Insight: Sort tasks by profit and greedily assign to workers with matching skills, using the super worker for the best remaining task

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The key insight is to use a greedy approach: sort tasks by profit descending and assign high-profit tasks to available workers first. The super worker gets the highest-profit task that regular workers can't handle. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Optimal - Maximum Bipartite Matching	O(n²m)	O(nm)	Use Hungarian algorithm or maximum bipartite matching to find optimal assignment
Greedy - Sort by Profit	O(n log n + m log m)	O(n + m)	Sort tasks by profit and greedily assign highest-profit tasks first
Brute Force - Try All Assignments	O(2^(n+m))	O(n+m)	Generate all possible task assignments and find maximum profit

Optimal - Maximum Bipartite Matching — Algorithm Steps

Create bipartite graph with workers and tasks
Add super worker connected to all tasks
Find maximum weighted matching
Return total profit from optimal matching

Visualization

Tap to expand

Step-by-Step Walkthrough

Model Graph

Create bipartite graph with workers and tasks

Find Matching

Use algorithm to find maximum weighted matching

Optimal Solution

Return profit from optimal assignment

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int skill;
    int profit;
    int index;
} Task;

int compareProfit(const void* a, const void* b) {
    Task* taskA = (Task*)a;
    Task* taskB = (Task*)b;
    return taskB->profit - taskA->profit;
}

int solution(int* workers, int workerCount, int tasks[][2], int taskCount) {
    // Count available workers by skill
    int workerSkillCount[1001] = {0};
    for (int i = 0; i < workerCount; i++) {
        if (workers[i] <= 1000) workerSkillCount[workers[i]]++;
    }
    
    // Sort tasks by profit descending
    Task* sortedTasks = (Task*)malloc(taskCount * sizeof(Task));
    for (int i = 0; i < taskCount; i++) {
        sortedTasks[i].skill = tasks[i][0];
        sortedTasks[i].profit = tasks[i][1];
        sortedTasks[i].index = i;
    }
    qsort(sortedTasks, taskCount, sizeof(Task), compareProfit);
    
    int totalProfit = 0;
    bool* usedTasks = (bool*)calloc(taskCount, sizeof(bool));
    int superTask = -1;
    int maxSuperProfit = 0;
    
    // First pass: assign to regular workers
    for (int i = 0; i < taskCount; i++) {
        int skill = sortedTasks[i].skill;
        int profit = sortedTasks[i].profit;
        int taskIdx = sortedTasks[i].index;
        
        if (skill <= 1000 && workerSkillCount[skill] > 0) {
            workerSkillCount[skill]--;
            totalProfit += profit;
            usedTasks[taskIdx] = true;
        } else {
            // Track best task for super worker
            if (profit > maxSuperProfit) {
                maxSuperProfit = profit;
                superTask = taskIdx;
            }
        }
    }
    
    // Assign best remaining task to super worker
    if (superTask != -1) {
        totalProfit += maxSuperProfit;
    }
    
    free(sortedTasks);
    free(usedTasks);
    return totalProfit;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    int workers[1000];
    int workerCount = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        workers[workerCount++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    int tasks[1000][2];
    int taskCount = 0;
    char* ptr = line + 1;
    while (*ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            tasks[taskCount][0] = atoi(ptr);
            while (*ptr != ',') ptr++;
            ptr++;
            tasks[taskCount][1] = atoi(ptr);
            taskCount++;
            while (*ptr != ']') ptr++;
            ptr++;
        } else {
            ptr++;
        }
    }
    
    printf("%d\n", solution(workers, workerCount, tasks, taskCount));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²m)

Maximum bipartite matching using Hungarian algorithm takes O(n²m) time

⚠ Quadratic Growth

Space Complexity

O(nm)

Bipartite graph representation requires O(nm) space for adjacency matrix

⚡ Linearithmic Space

34.2K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimal - Maximum Bipartite Matching — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler