[C++/Java/Python] Sort and Two pointer
Solution 1\n1. zip difficulty and profit as jobs.\n2. sort jobs and sort \'worker\'.\n3. Use 2 pointers. For each worker, find his maximum profit best he can ma
# Solution 1\n1. zip `difficulty` and `profit` as jobs.\n2. sort `jobs` and sort \'worker\'.\n3. Use 2 pointers. For each worker, find his maximum profit `best` he can make under his ability.\n<br>\n\nBecause we have sorted `jobs` and `worker`,\nwe will go through two lists only once.\nthis will be only `O(D + W)`.\n`O(DlogD + WlogW)`, as we sort jobs.\n<br>\n\n**C++**\n```cpp\n    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {\n        vector<pair<int, int>> jobs;\n        int N = profit.size(), res = 0, i = 0, best = 0;\n        for (int j = 0; j < N; ++j)\n            jobs.push_back(make_pair(difficulty[j], profit[j]));\n        sort(jobs.begin(), jobs.end());\n        sort(worker.begin(), worker.end());\n        for (int & ability : worker) {\n            while (i < N && ability >= jobs[i].first)\n                best = max(jobs[i++].second, best);\n            res += best;\n        }\n        return res;\n    }\n```\n\n**Java:**\n```java\n    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {\n        List<Pair<Integer, Integer>> jobs = new ArrayList<>();\n        int N = profit.length, res = 0, i = 0, best = 0;\n        for (int j = 0; j < N; ++j)\n            jobs.add(new Pair<Integer, Integer>(difficulty[j], profit[j]));\n        Collections.sort(jobs, Comparator.comparing(Pair::getKey));\n        Arrays.sort(worker);\n        for (int ability : worker) {\n            while (i < N && ability >= jobs.get(i).getKey())\n                best = Math.max(jobs.get(i++).getValue(), best);\n            res += best;\n        }\n        return res;\n    }\n```\n\n**Python:**\n```python\n    def maxProfitAssignment(self, difficulty, profit, worker):\n        jobs = sorted(zip(difficulty, profit))\n        res = i = best = 0\n        for ability in sorted(worker):\n            while i < len(jobs) and ability >= jobs[i][0]:\n                best = max(jobs[i][1], best)\n                i += 1\n            res += best\n        return res\n\n```\n<br>\n\n# Solution 2\n1. Use a treemap<difficulty, profit>\n2. Go through the treemap once, find the max profit `best` for each difficulty.\nTime `O(DlogD + WlogD)`\n<br>\n\n**Java**\n```java\n    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {\n        TreeMap<Integer, Integer> map = new TreeMap<>();\n        map.put(0, 0);\n        for (int i = 0; i < difficulty.length; i++) {\n            map.put(difficulty[i], Math.max(profit[i], map.getOrDefault(difficulty[i], 0)));\n        }\n        int best = 0, res = 0;\n        for (Integer key : map.keySet()) {\n            best = Math.max(map.get(key), best);\n            map.put(key, best);\n        }\n        for (int i = 0; i < worker.length; i++) {\n            res += map.floorEntry(worker[i]).getValue();\n        }\n        return res;\n    }\n```\n**C++**\n```cpp\n    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {\n        int N = profit.size(), res = 0, i = 0, best = 0;\n        map<int, int> jobs;\n        jobs[0] = 0;\n        for (int j = 0; j < N; ++j)\n            jobs[difficulty[j]] = max(jobs[difficulty[j]], profit[j]);\n        for (auto &it: jobs)\n            it.second = best = max(best, it.second);\n        for (int & ability : worker)\n            res += (--jobs.upper_bound(ability))->second;\n        return res;\n    }\n```\n
[]