[Greedy + Tutorial] Most Profit Assigning Work
Topic :  Greedy\nGreedy algorithms are a class of algorithms that make locally optimal choices at each step with the hope of finding a global optimum solution. 
**Topic** :  Greedy\nGreedy algorithms are a class of algorithms that make locally optimal choices at each step with the hope of finding a global optimum solution. In these algorithms, decisions are made based on the information available at the current moment without considering the consequences of these decisions in the future. The key idea is to select the best possible choice at each step, leading to a solution that may not always be the most optimal but is often good enough for many problems. (GFG Reference)\n\n___\n\n## Solution\nThe **greedy intuition** suggests that each worker should be assigned the project that offers the maximum profit within their capability.\n\nLet\'s first sort projects based on their difficulty in ascending order. Worker `i` can complete all projects  `[0 : j]` such that the difficulty of `projects[j]` is less than or equal to `worker[i]`. We can select the project with the maximum profit from the subset of projects with indices ranging from `0` to `j`.\n\nTo improve efficiency, sorting the worker array allows us to implement a two-pointer algorithm efficiently. We maintain a variable `j` to indicate the index of the projects that are available to worker `i`, and `maxProfit` to denote the maximum profit that can be earned among these projects. \n\nSince all workers are sorted in ascending order `worker[i] <= worker[i + 1]`, variable `j` and` maxProfit` will only increase. Therefor,  we can efficiently apply a two-pointer approach with O(n) complexity.\n\n\n```c++ []\nclass Solution {\npublic:\n    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {\n        int ans = 0;\n        vector<pair<int, int>> jobs;\n        for(int i = 0; i < difficulty.size(); i++) {\n            jobs.push_back({difficulty[i], profit[i]});\n        }\n        \n        sort(jobs.begin(), jobs.end());\n        sort(worker.begin(), worker.end());\n        for(int i = 0, j = 0, maxProfit = 0; i < worker.size(); i++) {\n            while(j < jobs.size() && jobs[j].first <= worker[i]) {\n                maxProfit = max(maxProfit, jobs[j].second);\n                j++;\n            }\n            ans += maxProfit;\n        }\n        return ans;\n    }\n};\n```\n```java []\nclass Solution {\n    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {\n        int ans = 0;\n        List<int[]> jobs = new ArrayList<>();\n        \n        for (int i = 0; i < difficulty.length; i++) {\n            jobs.add(new int[]{difficulty[i], profit[i]});\n        }\n        \n        Collections.sort(jobs, (a, b) -> Integer.compare(a[0], b[0]));\n        Arrays.sort(worker);\n        \n        for (int i = 0, j = 0, maxProfit = 0; i < worker.length; i++) {\n            while (j < jobs.size() && jobs.get(j)[0] <= worker[i]) {\n                maxProfit = Math.max(maxProfit, jobs.get(j)[1]);\n                j++;\n            }\n            ans += maxProfit;\n        }\n        \n        return ans;\n    }\n}\n```\n```python []\nclass Solution:\n    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n        ans = 0\n        jobs = sorted(zip(difficulty, profit))\n        worker.sort()\n        \n\t\tj, maxProfit = 0, 0\n        for i in range(len(worker)):\n            while j < len(jobs) and jobs[j][0] <= worker[i]:\n                maxProfit = max(maxProfit, jobs[j][1])\n                j += 1\n            ans += maxProfit\n        \n        return ans\n```\n```Go []\nfunc maxProfitAssignment(difficulty []int, profit []int, worker []int) int {\n    ans := 0\n    jobs := make([][2]int, len(difficulty))\n    \n    for i := 0; i < len(difficulty); i++ {\n        jobs[i] = [2]int{difficulty[i], profit[i]}\n    }\n    \n    sort.Slice(jobs, func(i, j int) bool {\n        return jobs[i][0] < jobs[j][0]\n    })\n    sort.Ints(worker)\n    \n    j := 0\n    maxProfit := 0\n    for i := 0; i < len(worker); i++ {\n        for j < len(jobs) && jobs[j][0] <= worker[i] {\n            maxProfit = max(maxProfit, jobs[j][1])\n            j++\n        }\n        ans += maxProfit\n    }\n    \n    return ans\n}\n```\n```PHP []\nclass Solution {\n\n    /**\n     * @param Integer[] $difficulty\n     * @param Integer[] $profit\n     * @param Integer[] $worker\n     * @return Integer\n     */\n    function maxProfitAssignment($difficulty, $profit, $worker) {\n        $ans = 0;\n        $jobs = array();\n        \n        for ($i = 0; $i < count($difficulty); $i++) {\n            $jobs[] = array($difficulty[$i], $profit[$i]);\n        }\n        \n        usort($jobs, function($a, $b) {\n            return $a[0] - $b[0];\n        });\n        \n        sort($worker);\n        \n        $j = 0;\n        $maxProfit = 0;\n        \n        for ($i = 0; $i < count($worker); $i++) {\n            while ($j < count($jobs) && $jobs[$j][0] <= $worker[$i]) {\n                $maxProfit = max($maxProfit, $jobs[$j][1]);\n                $j++;\n            }\n            $ans += $maxProfit;\n        }\n        \n        return $ans;\n    }\n}\n```\n```javascript []\n/**\n * @param {number[]} difficulty\n * @param {number[]} profit\n * @param {number[]} worker\n * @return {number}\n */\nvar maxProfitAssignment = function(difficulty, profit, worker) {\n    let ans = 0;\n    let jobs = [];\n    \n    for (let i = 0; i < difficulty.length; i++) {\n        jobs.push([difficulty[i], profit[i]]);\n    }\n    \n    jobs.sort((a, b) => a[0] - b[0]);\n    worker.sort((a, b) => a - b);\n    \n    let j = 0;\n    let maxProfit = 0;\n    \n    for (let i = 0; i < worker.length; i++) {\n        while (j < jobs.length && jobs[j][0] <= worker[i]) {\n            maxProfit = Math.max(maxProfit, jobs[j][1]);\n            j++;\n        }\n        ans += maxProfit;\n    }\n    \n    return ans;\n};\n```\n\n\n**Complexity**:\n* Time Complexity : `O(max(n log n, m log m))`\n* Space Complexity : `O(n)`\n\n**Feel free to leave a comment if something is confusing, or if you have any suggestions on how I can improve the post.**
['Greedy', 'C', 'PHP', 'Sorting', 'Python', 'Java', 'Go', 'JavaScript']