Most Profit Assigning Work - Practice Coding Problems

Most Profit Assigning Work - Problem

You have n jobs and m workers. You are given three arrays:

difficulty[i] and profit[i] are the difficulty and profit of the i-th job
worker[j] is the ability of the j-th worker (can only complete jobs with difficulty ≤ worker[j])

Rules:

Every worker can be assigned at most one job
One job can be completed multiple times by different workers
If a worker cannot complete any job, their profit is 0

Return the maximum profit we can achieve after assigning workers to jobs optimally.

Input & Output

Example 1 — Basic Assignment

$ Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]

› Output: 100

💡 Note: Worker 1 (ability=4): can do jobs 1,2 → best profit=20. Worker 2 (ability=5): can do jobs 1,2 → best profit=20. Worker 3 (ability=6): can do jobs 1,2,3 → best profit=30. Worker 4 (ability=7): can do jobs 1,2,3 → best profit=30. Total: 20+20+30+30=100

Example 2 — Some Workers Get No Job

$ Input: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]

› Output: 0

💡 Note: All workers have abilities (40,25,25) but minimum job difficulty is 47. No worker can complete any job, so total profit is 0.

Example 3 — Multiple Workers Same Job

$ Input: difficulty = [68,35,52], profit = [90,17,68], worker = [79,45,85]

› Output: 324

💡 Note: Worker 1 (ability=79): can do all jobs → best profit=90. Worker 2 (ability=45): can do job 2 only (diff=35) → profit=17. Worker 3 (ability=85): can do all jobs → best profit=90. Total: 90+17+90+127=324. Wait, let me recalculate: Worker 1: jobs with diff≤79 are all three, max profit=90. Worker 2: jobs with diff≤45 is job 2 (diff=35), profit=17. Worker 3: jobs with diff≤85 are all three, max profit=90. Total: 90+17+90=197

Constraints

1 ≤ difficulty.length ≤ 10⁴
1 ≤ profit.length ≤ 10⁴
difficulty.length = profit.length
1 ≤ worker.length ≤ 10⁴
1 ≤ difficulty[i], profit[i], worker[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Jobs with difficulty/profit pairs and workers with abilities

Matching

Each worker gets the highest-paying job they can complete

Output

Total profit from optimal job assignments

Key Takeaway

🎯 Key Insight: Sort jobs by difficulty and precompute maximum profits to enable efficient binary search per worker

Asked in

G Google 12 A Amazon 8 f Facebook 6 M Microsoft 5

The key insight is to preprocess jobs by sorting them by difficulty and precomputing maximum profits at each level. This allows us to use binary search to find the best job for each worker in O(log n) time. Best approach achieves O(n log n + m log n) time complexity with O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Precompute Maximum Profits	O(n log n + m log n)	O(n)	Sort jobs, precompute maximum profit at each difficulty level, then binary search for each worker
Sort Jobs by Difficulty	O(n log n + m×n)	O(n)	Sort jobs by difficulty, then for each worker use binary search to find applicable jobs
Brute Force - Check All Jobs	O(n×m)	O(1)	For each worker, check all jobs to find the highest profit they can achieve

Precompute Maximum Profits — Algorithm Steps

Sort jobs by difficulty
Precompute max profit up to each difficulty
For each worker, binary search difficulty range
Return precomputed max profit

Visualization

Tap to expand

Step-by-Step Walkthrough

Preprocess

Sort jobs and compute maximum profit up to each difficulty

Binary Search

For each worker, find highest manageable difficulty in O(log n)

Instant Lookup

Get precomputed maximum profit for that difficulty level

Code -

solution.c — C

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

typedef struct {
    int difficulty;
    int profit;
} Job;

int compareJobs(const void* a, const void* b) {
    Job* jobA = (Job*)a;
    Job* jobB = (Job*)b;
    return jobA->difficulty - jobB->difficulty;
}

int solution(int* difficulty, int diffSize, int* profit, int profitSize, int* worker, int workerSize) {
    // Create job pairs and sort by difficulty
    Job* jobs = malloc(diffSize * sizeof(Job));
    for (int i = 0; i < diffSize; i++) {
        jobs[i].difficulty = difficulty[i];
        jobs[i].profit = profit[i];
    }
    qsort(jobs, diffSize, sizeof(Job), compareJobs);
    
    // Precompute maximum profit up to each difficulty
    int maxProfitSoFar = 0;
    for (int i = 0; i < diffSize; i++) {
        if (jobs[i].profit > maxProfitSoFar) {
            maxProfitSoFar = jobs[i].profit;
        }
        jobs[i].profit = maxProfitSoFar;
    }
    
    int totalProfit = 0;
    
    for (int i = 0; i < workerSize; i++) {
        // Binary search for the highest difficulty this worker can handle
        int left = 0, right = diffSize;
        while (left < right) {
            int mid = (left + right) / 2;
            if (jobs[mid].difficulty <= worker[i]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (left > 0) {
            totalProfit += jobs[left - 1].profit;
        }
    }
    
    free(jobs);
    return totalProfit;
}

int* parseArray(char* str, int* size) {
    int* arr = malloc(1000 * sizeof(int));
    *size = 0;
    char* token = strtok(str, "[],");
    while (token != NULL) {
        arr[(*size)++] = atoi(token);
        token = strtok(NULL, "[],");
    }
    return arr;
}

int main() {
    char line[10000];
    
    fgets(line, sizeof(line), stdin);
    int diffSize;
    int* difficulty = parseArray(line, &diffSize);
    
    fgets(line, sizeof(line), stdin);
    int profitSize;
    int* profit = parseArray(line, &profitSize);
    
    fgets(line, sizeof(line), stdin);
    int workerSize;
    int* worker = parseArray(line, &workerSize);
    
    printf("%d\n", solution(difficulty, profit, diffSize, profit, profitSize, worker, workerSize));
    
    free(difficulty);
    free(profit);
    free(worker);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + m log n)

O(n log n) to sort jobs and precompute profits, O(m log n) for binary search per worker

⚡ Linearithmic

Space Complexity

O(n)

Additional arrays for sorted jobs and precomputed maximum profits

⚡ Linearithmic Space

32.5K 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

Precompute Maximum Profits — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler