Most Profit Assigning Work Problem from Leetcode (Problem no. 826)

338 Views Asked by At

I have been trying to solve this problem on leetcode (https://leetcode.com/problems/most-profit-assigning-work/) whose problem description goes like this :

We have jobs: difficulty[i] is the difficulty of the ith job, and profit[i] is the profit of the ith job. Now we have some workers. worker[i] is the ability of the ith worker, which means that this worker can only complete a job with difficulty at most worker[i].
Every worker can be assigned at most one job, but one job can be completed multiple times. For example, if 3 people attempt the same job that pays $1, then the total profit will be $3. If a worker cannot complete any job, his profit is $0. What is the most profit we can make?
For example : Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7] Output: 100
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get profit of [20,20,30,30] separately.

I have tried solving using this code,

class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {

        map <int,int> map;
        int sum = 0;
        int j = 0;
        
        // creating a hash map for profit and difficulty
        for (int i = 0; i < profit.size(); i++) {
            map.insert({profit[i], difficulty[i]});
        }
  
        //sorting the workers vector in descending order
        sort(worker.begin(), worker.end(),  greater<int>());

        //Iterating through the hash map in descending order of Profit (high profit to low profit) 
        for (auto i = map.rbegin(); i != map.rend(); i++) {

            // Assigning the job with higher profit to the workers who have difficulty
            // greater than equal to the difficulty of the job
            while(j < worker.size()) {
                if (worker[j] >= (i->second)) {
                    sum += i->first;
                    j++;
                } else {
                    break;
                }                
            }
        }
        return sum; 
    }
};

But my code isn't passing a test case. I'm attaching the link to the test case. https://notepad.pw/r7dv12cv (It is too big to paste here)

My output       : 999481607
Expected output : 999542181

I'm unable to find where the issue is arising. It has passed all the test cases except this.
Please go through the code and run it on leetcode platform if you can. Please let me know where I have gone wrong.

0

There are 0 best solutions below