algoadvance

Leetcode 826. Most Profit Assigning Work

Problem Statement

You have n jobs and m workers. You are given three input arrays difficulty, profit, and worker where:

Each worker can be assigned at most one job, but only if the job’s difficulty is at most the worker’s ability. Each worker wants to maximize their profit by doing a job with the highest profit for which they can handle the difficulty.

Return the maximum profit we can achieve.

Clarifying Questions

  1. How is the input size?
    • difficulty, profit, and worker are all integer arrays where 1 <= difficulty.length == profit.length <= 10^4 and 1 <= worker.length <= 10^4.
  2. Are the values in difficulty, profit, and worker constrained?
    • Yes, each value (difficulty[i], profit[i], worker[j]) is in the range [1, 10^5].
  3. Can there be multiple jobs with the same difficulty and different profits?
    • Yes, it can happen, which means each job is distinct.
  4. What should be returned?
    • The total profit sum we can achieve by assigning jobs to workers optimally.

Strategy

  1. Pair Sorting:
    • Combine the difficulty and profit arrays and sort the pairs by difficulty.
  2. Prefix Maximum Array:
    • Create a prefix maximum array such that maxProfit[i] stores the maximum profit achievable up to the i-th job when sorted by difficulty.
  3. Worker Assignment:
    • Sort the worker array.
    • For each worker, use binary search (or two-pointer technique) to find the most difficult job they can handle and use the maxProfit array to get the maximum profit for that difficulty.

Implementation

#include <vector>
#include <algorithm>
using namespace std;

int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
    int n = difficulty.size();
    vector<pair<int, int>> jobs;
    
    for (int i = 0; i < n; ++i) {
        jobs.push_back({difficulty[i], profit[i]});
    }
    
    // Sort jobs by difficulty
    sort(jobs.begin(), jobs.end());
    
    // Prefix maximum profit array
    vector<int> maxProfits(n);
    maxProfits[0] = jobs[0].second;
    
    for (int i = 1; i < n; ++i) {
        maxProfits[i] = max(maxProfits[i - 1], jobs[i].second);
    }
    
    // Sort worker by their ability
    sort(worker.begin(), worker.end());
    
    int maxTotalProfit = 0;
    int j = 0; // To track the current job index
    
    for (int ability : worker) {
        while (j < n && jobs[j].first <= ability) {
            ++j;
        }
        if (j > 0) {
            maxTotalProfit += maxProfits[j - 1];
        }
    }
    
    return maxTotalProfit;
}

Time Complexity

Thus, the overall time complexity is: [ O(n \log n + m \log m + n + m) \approx O((n + m) \log (n + m)) ]

This is efficient for the given constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI