✅[C++/Java/Python] Two Approaches Greedy Approach and Map Approach #Optimal Solution
Intuition\n Describe your first thoughts on how to solve this problem. \n### 1. Understanding Workers and Jobs:\n\n- Workers: These are individuals who have dif
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n### **1. Understanding Workers and Jobs:**\n\n- **Workers**: These are individuals who have different skill levels. Each worker can handle jobs up to a certain difficulty level.\n- **Jobs**: Each job has a specific difficulty level and a profit associated with it. The higher the profit, the more money is earned by completing that job.\n\n### **2. Goal**: \n- The main objective is to assign jobs to workers in such a way that the total profit is maximized. This means we want each worker to do the job that gives the most money, given their skill level.\n\n### **3. Constraints**:\n- **One Job per Worker**: Each worker can only do one job.\n- **Job Repetition**: The same job can be completed by multiple workers. This means if a job is very profitable and many workers can handle it, they all can be assigned to that job.\n\n### **4. Steps to Solve the Problem**:\n\n1. **List All Jobs and Their Profits**: \n    - Identify all available jobs along with their respective difficulty levels and profits.\n\n2. **Match Workers to Jobs**: \n    - For each worker, look at the jobs they can do based on their skill level.\n    - Among the jobs they can do, find the one with the highest profit.\n    \n3. **Assign the Best Job**:\n    - Assign that most profitable job to the worker.\n    - Repeat this for each worker until all workers have a job assigned.\n\n---\n\n\n# Approach 1 : Optimizing Job Assignment for Maximum Profit Using Sorting and Two-Pointer Technique\n<!-- Describe your approach to solving the problem. -->\n1. **Sorting the Workers**:\n    - First, we sort the `worker` array in ascending order. This allows us to assign jobs to workers starting from the least skilled to the most skilled.\n    ``` \n    sort(worker.begin(),worker.end());\n    // sorting the woker vector in non decreasing order.\n    ```\n\n2. **Pairing and Sorting Jobs**: \n\n    - We create a vector of pairs called `jobs`, where each pair consists of a job\'s difficulty and its associated profit.\n    ```\n    // Declaration of the jobs vector\n    vector<pair<int,int>> jobs(totalJobs); \n\n    // Initialisation of the jobs vector\n    for(int i = 0; i < totalJobs; i++) {\n            jobs[i] = {difficulty[i],profit[i]};\n        }\n    ```\n    - We sort the `jobs` vector by difficulty. This allows us to efficiently match jobs to workers based on their skill levels.\n    ```\n    sort(jobs.begin(),jobs.end());\n    // Sorting the jobs vector\n    ```\n\n3. **Initializing Variables**:\n\n    - `maxProfitValue` is used to keep track of the maximum profit achievable for any job up to the current job being considered.\n    - `totalProfitCollected` accumulates the total profit from all workers.\n    - `currentWorker` and `currentJob` are indices used to traverse the worker and jobs vectors, respectively.\n    ```\n    int maxProfitValue = 0, \n        totalProfitCollected = 0, \n        currentWorker = 0, \n        currentJob = 0;\n    ```\n\n4. **Assigning Jobs to Workers**:\n\n    - We use a while loop to iterate through each worker.\n    - For each worker, we use another while loop to find all jobs that the worker can handle (i.e., jobs where the difficulty is less than or equal to the worker\'s skill level).\n    - As we consider each job, we update `maxProfitValue` to be the maximum profit achievable for the current worker.\n    - After determining the best job for the current worker, we add `maxProfitValue` to `totalProfitCollected`.\n    ``` \n    while(currentWorker < totalWorkers) {\n        while(currentJob < totalJobs && jobs[currentJob].first <= worker[currentWorker]) { \n            maxProfitValue = max(maxProfitValue,jobs[currentJob].second); \n            currentJob++;\n        }\n        totalProfitCollected += maxProfitValue;\n        currentWorker++;\n    }\n    ```\n\n5. **Returning the Result**:\n    - After processing all workers, we return `totalProfitCollected` as the total maximum profit.\n    ```\n    return totalProfitCollected;\n    ```\n    \n---\n\n# Complexity:\n#### Time complexity: **O(WlogW+JlogJ)**\n\n#### Explanation :- \n- Sorting Workers: **O(Wlog\u2061W)**\n- Creating Jobs Vector: **O(J)**\n- Sorting Jobs: **O(JlogJ)**\n- Assigning Jobs: **O(W+J)**\n\nCombining these steps, the overall time complexity is: **O(WlogW)+O(J)+O(JlogJ)+O(W+J)**\n\nSince **O(W+J)** is linear and dominated by the sorting steps, we can simplify the total time complexity to: **O(WlogW+JlogJ)**\nTherefore, the time complexity of the provided code is: **O(WlogW+JlogJ)**\n\u200B\n\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n#### Space complexity: **O(J+W)**\n#### Explanation :- \n- Input Arrays: **O(J)+O(J)+O(W)=O(J+W)**\n- Jobs Vector: **O(J)**\n- Auxiliary Variables: **O(1)**\n\nCombining these, the total space complexity is: **O(J+W)**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n``` C++ []\nclass Solution {\npublic:\n    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {\n        // sorting the workers with their increasing ability difficulty\n        sort(worker.begin(),worker.end()); \n        int totalWorkers = worker.size(), totalJobs = difficulty.size();\n        vector<pair<int,int>> jobs(totalJobs); \n        // storing the job difficulty and its profit\n        for(int i = 0; i < totalJobs; i++) {\n            jobs[i] = {difficulty[i],profit[i]};\n        }\n        // Sorting the jobs based on their increasing difficulties because we want that workers with less abilities should have the first chance to choose their job from the jobs available and select the one which they can done and grab max profit.\n        sort(jobs.begin(),jobs.end());\n        int maxProfitValue = 0, totalProfitCollected = 0, currentWorker = 0, currentJob = 0;\n        while(currentWorker < totalWorkers) {\n            // While the currentJob count is less than the total jobs available and also the current job difficulty is less than or equal to the ability of the current worker, he/she can choose the job and grab the maximum profit out of it.\n            while(currentJob < totalJobs && jobs[currentJob].first <= worker[currentWorker]) { \n                // Storing the maximum profit achieved till now.\n                maxProfitValue = max(maxProfitValue,jobs[currentJob].second); \n                // Switching to the next available job.\n                currentJob++;\n            }\n            // Storing the totalProfitCollected by each of the workers.\n            totalProfitCollected += maxProfitValue;\n            // Doing same thing for the next Worker.\n            currentWorker++;\n        }\n        // Returning the totalProfitCollected.\n        return totalProfitCollected;\n    }\n};\n```\n\n``` Java []\nclass Solution {\n    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {\n        Arrays.sort(worker);\n        int totalWorkers = worker.length;\n        int totalJobs = difficulty.length;\n        List<int[]> jobs = new ArrayList<>();\n        for (int i = 0; i < totalJobs; i++) {\n            jobs.add(new int[]{difficulty[i], profit[i]});\n        }\n        jobs.sort((a, b) -> a[0] - b[0]);\n\n        int maxProfitValue = 0, totalProfitCollected = 0;\n        int currentWorker = 0, currentJob = 0;\n        while (currentWorker < totalWorkers) {\n            while (currentJob < totalJobs && jobs.get(currentJob)[0] <= worker[currentWorker]) {\n                maxProfitValue = Math.max(maxProfitValue, jobs.get(currentJob)[1]);\n                currentJob++;\n            }\n            totalProfitCollected += maxProfitValue;\n            currentWorker++;\n        }\n        return totalProfitCollected;\n    }\n}\n```\n``` Python3 []\nclass Solution:\n    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n        worker.sort()\n        jobs = sorted(zip(difficulty, profit))\n        \n        max_profit_value = 0\n        total_profit_collected = 0\n        current_job = 0\n        total_jobs = len(jobs)\n\n        for ability in worker:\n            while current_job < total_jobs and jobs[current_job][0] <= ability:\n                max_profit_value = max(max_profit_value, jobs[current_job][1])\n                current_job += 1\n            total_profit_collected += max_profit_value\n        \n        return total_profit_collected\n   \n```\n``` C []\nint cmp(const void *a, const void *b) {\n    return (*(int *)a - *(int *)b);\n}\n\nint cmpJobs(const void *a, const void *b) {\n    int *jobA = *(int **)a;\n    int *jobB = *(int **)b;\n    return jobA[0] - jobB[0];\n}\n\nint maxProfitAssignment(int* difficulty, int difficultySize, int* profit, int profitSize, int* worker, int workerSize) {\n    qsort(worker, workerSize, sizeof(int), cmp);\n    int **jobs = (int **)malloc(difficultySize * sizeof(int *));\n    for (int i = 0; i < difficultySize; i++) {\n        jobs[i] = (int *)malloc(2 * sizeof(int));\n        jobs[i][0] = difficulty[i];\n        jobs[i][1] = profit[i];\n    }\n    qsort(jobs, difficultySize, sizeof(int *), cmpJobs);\n\n    int maxProfitValue = 0, totalProfitCollected = 0;\n    int currentWorker = 0, currentJob = 0;\n\n    while (currentWorker < workerSize) {\n        while (currentJob < difficultySize && jobs[currentJob][0] <= worker[currentWorker]) {\n            if (jobs[currentJob][1] > maxProfitValue) {\n                maxProfitValue = jobs[currentJob][1];\n            }\n            currentJob++;\n        }\n        totalProfitCollected += maxProfitValue;\n        currentWorker++;\n    }\n\n    for (int i = 0; i < difficultySize; i++) {\n        free(jobs[i]);\n    }\n    free(jobs);\n\n    return totalProfitCollected;\n}\n```\n``` JavaScript []\n/**\n * @param {number[]} difficulty\n * @param {number[]} profit\n * @param {number[]} worker\n * @return {number}\n */\nvar maxProfitAssignment = function maxProfitAssignment(difficulty, profit, worker) {\n    worker.sort((a, b) => a - b);\n    let jobs = difficulty.map((d, i) => [d, profit[i]]);\n    jobs.sort((a, b) => a[0] - b[0]);\n\n    let maxProfitValue = 0, totalProfitCollected = 0;\n    let currentJob = 0;\n    let totalJobs = jobs.length;\n\n    worker.forEach(ability => {\n        while (currentJob < totalJobs && jobs[currentJob][0] <= ability) {\n            maxProfitValue = Math.max(maxProfitValue, jobs[currentJob][1]);\n            currentJob++;\n        }\n        totalProfitCollected += maxProfitValue;\n    });\n\n    return totalProfitCollected;\n};\n```\n---\n\n# Approach 2 : Maximizing Worker Profit through Job Difficulty Mapping and Efficient Lookup\n1. **Initialize Variables and Data Structures**:\n\n    - **numJobs**: The number of jobs available.\n    - **totalProfit**: To accumulate the total profit earned by all workers.\n    - **bestProfit**: To keep track of the best profit seen so far for any difficulty level.\n    - **jobMap**: A map where the keys are job difficulties and the values are the maximum profits for those difficulties. It\'s initialized with a dummy job `{0, 0}`.\n    ```\n    int numJobs = profit.size(), totalProfit = 0, bestProfit = 0;\n    map<int, int> jobMap;\n    jobMap[0] = 0;\n    ```\n2. **Populate the Job Map**:\n\n    - Iterate through each job and update `jobMap` such that each difficulty level maps to the maximum profit for jobs of that difficulty.\n    - This ensures that if multiple jobs have the same difficulty, the job with the highest profit is stored.\n    ```\n    for (int j = 0; j < numJobs; ++j) {\n        jobMap[difficulty[j]] = max(jobMap[difficulty[j]], profit[j]);\n    }\n    ```\n\n3. **Update the Job Map for Best Profits**:\n    - Iterate through the `jobMap` and update each entry so that it reflects the best profit achievable for any job of that difficulty or less. This makes future lookups efficient.\n    ```\n    for (auto &it : jobMap) {\n        it.second = bestProfit = max(bestProfit, it.second);\n    }\n    ```\n\n4. **Assign Jobs to Workers**:\n\n    - For each worker, find the most profitable job they can handle. This is done using **upper_bound** on the `jobMap`.\n    - **upper_bound(skill)** finds the first entry with a difficulty greater than the worker\'s skill. By decrementing the iterator, we get the largest job difficulty that is less than or equal to the worker\'s skill.\n    - Add the profit of the selected job to the `totalProfit`.\n    ```\n    for (int &skill : worker) {\n        totalProfit += (--jobMap.upper_bound(skill))->second;\n    }\n    ```\n\n5. **Return the Total Profit**:\n    - After processing all workers, return the accumulated `totalProfit`.\n    ```\n    return totalProfit;\n    ```\n\n# Complexity:\n#### Time complexity: **O((J+W)logJ)**\n\n#### Explanation :- \n**Sorting and Map Operations**: The operations to populate and query the map are efficient, with the overall complexity being dominated by the map operations.\n**Total Complexity**: **O((J+W)logJ)**, where J is the number of jobs and \nW is the number of workers. This includes the time to build and query the map.\n\n\n#### Space complexity: **O(J+W)**\n#### Explanation :- \n- **Map Storage**: The map jobMap stores up to J entries.\n- **Input Storage**: The input arrays `difficulty`, `profit`, and `worker`use O(J), O(J), and O(W) space, respectively.\n- **Auxiliary Space**: O(1) for auxiliary variables.\n\n# Code\n``` C++ []\nclass Solution {\npublic:\n    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {\n        int numJobs = profit.size(), totalProfit = 0, bestProfit = 0;\n        map<int, int> jobMap;\n\n        // Initialize jobMap with a dummy job of 0 difficulty and 0 profit\n        jobMap[0] = 0;\n\n        // Populate the jobMap with the maximum profit for each difficulty\n        for (int j = 0; j < numJobs; ++j) {\n            jobMap[difficulty[j]] = max(jobMap[difficulty[j]], profit[j]);\n        }\n        \n        // Update jobMap to store the best profit achievable up to each difficulty\n        for (auto &it : jobMap) {\n            it.second = bestProfit = max(bestProfit, it.second);\n        }\n        \n        // Assign jobs to workers\n        for (int &skill : worker) {\n            totalProfit += (--jobMap.upper_bound(skill))->second;\n        }\n        \n        return totalProfit;\n    }\n};\n\n```\n``` Java []\nclass Solution {\n    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {\n        int numJobs = profit.length;\n        int totalProfit = 0;\n        int bestProfit = 0;\n        TreeMap<Integer, Integer> jobMap = new TreeMap<>();\n        \n        // Initialize jobMap with a dummy job of 0 difficulty and 0 profit\n        jobMap.put(0, 0);\n        \n        // Populate the jobMap with the maximum profit for each difficulty\n        for (int j = 0; j < numJobs; ++j) {\n            jobMap.put(difficulty[j], Math.max(jobMap.getOrDefault(difficulty[j], 0), profit[j]));\n        }\n        \n        // Update jobMap to store the best profit achievable up to each difficulty\n        for (Map.Entry<Integer, Integer> entry : jobMap.entrySet()) {\n            entry.setValue(bestProfit = Math.max(bestProfit, entry.getValue()));\n        }\n        \n        // Assign jobs to workers\n        for (int skill : worker) {\n            totalProfit += jobMap.floorEntry(skill).getValue();\n        }\n        \n        return totalProfit;\n    }\n}\n```\n\n![upvote.jpeg](https://assets.leetcode.com/users/images/ce196c66-2e6f-4dec-8e30-c25c2f1f7fd3_1706881698.9688694.jpeg)\n[Instagram](https://www.instagram.com/iamsidharthaa__/)\n[LinkedIn](https://www.linkedin.com/in/sidharth-jain-36b542133)\n**If you find this solution helpful, consider giving it an upvote! Your support is appreciated. Keep coding, stay healthy, and may your programming endeavors be both rewarding and enjoyable!**
['Array', 'Two Pointers', 'Binary Search', 'Greedy', 'C', 'Sorting', 'C++', 'Java', 'Python3', 'JavaScript']