826. Most Profit Assigning Work

 

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?

Example 1:

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] seperately.

Notes:

  • 1 <= difficulty.length = profit.length <= 10000
  • 1 <= worker.length <= 10000
  • difficulty[i], profit[i], worker[i]  are in range [1, 10^5]

 

这道题给了我们一堆工作,每个工作有不同的难度,且对应着不同的利润。现在还有一些工人,每个人能胜任工作的难度不同,题目说了没人最多只能干一项工作,但是每个工作可以被多个人做。现在问我们这些工人能产生的最大利润。题目中给了一个例子,但是这个例子会给我们一些错觉,实际上difficulty数组不一定是有序的,而且可能有相同难度的工作对应不同的利润。还有就是,难度大的工作不一定利润就大,忽略了这些隐藏条件,很容易做错。为了快速的知道每个工作的难度和其对应的利润,我们可以建立难度和利润的之间映射,由于前面说了,相同的难度可能有不同的利润,所以我们希望难度映射到最高的利润,所以每次都跟自身的映射值比较一下,保留较大值即可。同时,我们还希望工作的难度能排个序,这样就可以根据工人的能力值来快速搜索能做的工作了,所以可以使用TreeMap。但是,还有个问题,前面说了难度大的工作不一定利润就大,所以我们希望难度映射的利润,是不大于其难度的工作的利润中的最大值,所以我们还要遍历一遍所有的映射,维护一个当前最大值cur,然后不断的更新每个工作的利润,同时也更新当前最大值。这些都建立好了后,之后就简单了,我们遍历每个工人,根据其能力值,来二分查第一个难度值大于该能力值的工作,可以用内置的 upper_bound 函数,如果结果第一个数字,那么我们将其前面一个难度的工作的利润加入结果res即可,参见代码如下:

 

解法一:

class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        int res = 0, cur = 0;
        map<int, int> m;
        for (int i = 0; i < difficulty.size(); ++i) {
            m[difficulty[i]] = max(m[difficulty[i]], profit[i]);
        }
        for (auto &a : m) {
            a.second = max(a.second, cur);
            cur = a.second;
        }
        for (int i = 0; i < worker.size(); ++i) {
            auto it = m.upper_bound(worker[i]);
            if (it != m.begin()) {
                res += (--it)->second;
            }
        }
        return res;
    }
};

 

我们也可以不用TreeMap,而是将难度和利润组成pair,加入到一个数组中,那么就算相同的难度对应不同的利润,也不会丢失数据。我们还是根据难度给所有的工作排个序,同时,我们按能力也给工人排个序,从能力低的工人开始分配工作,这样我们只需要遍历一次所有的工作,因为当能力低的工人分配了某个工作时,后面能力高的工人不需要再考虑之前的工作,因为工作已经按难度排好序了,只需要从当前位置继续往后面匹配工作,我们可以使用一个全局变量i,当工人的能力值大于等于某个工作的难度时,我们用其来更新curMax,这里的curMax记录当前工人能做的工作的最大利润,这样当工作遍历完了,或者当前工作难度已经大于工人的能力值了时就停止,这样curMax就是该工人能获得的利润,加入结果res,参见代码如下:

 

解法二:

class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        int res = 0, n = profit.size(), curMax = 0, i = 0;
        vector<pair<int, int>> jobs;
        for (int j = 0; j < n; ++j) {
            jobs.push_back({difficulty[j], profit[j]});
        }
        sort(jobs.begin(), jobs.end());
        sort(worker.begin(), worker.end());
        for (int ability : worker) {
            while (i < n && ability >= jobs[i].first) {
                curMax = max(curMax, jobs[i++].second);
            }
            res += curMax;
        }
        return res;
    }
};

 

我们还可以使用动态规划Dynamic Programming来做,建立一个一维的dp数组,这里的dp[i]表示能力为i的工人所能获得的最大的利润。dp数组大小初始化为100001,这是题目中给定的范围,然后我们用给定的工作的难度和利润来更新dp数组,跟解法一中的更新TreeMap有些像,要考虑相同的难度可能有不同的利润,所以每次更新的时候要跟本身比较。之后就是从1开始更新dp本身,dp[i]跟前面一个dp值比较,取较大值更新dp[i],这个操作跟解法一中的那个更新TreeMap的映射值的操作是一样的,都是为了避免难度高的工作利润低。这里的dp数组cover了所有的能力值的范围,这样对于任何一个工人,我们可以根据其能力值马上找出其可以获得的最大利润,而不用像解法一中要使用二分查找,我们牺牲了空间,换来了常数级的查找速度,参见代码如下:

 

解法三:

class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        int res = 0, n = profit.size();
        vector<int> dp(100001);
        for (int i = 0; i < n; ++i) {
            dp[difficulty[i]] = max(dp[difficulty[i]], profit[i]);
        }   
        for (int i = 1; i < dp.size(); ++i) {
            dp[i] = max(dp[i], dp[i - 1]);
        }
        for (int ability : worker) {
            res += dp[ability];
        }
        return res;
    }
};

 

参考资料:

https://leetcode.com/problems/most-profit-assigning-work/

https://leetcode.com/problems/most-profit-assigning-work/discuss/127133/Java-Solution-with-TreeMap

https://leetcode.com/problems/most-profit-assigning-work/discuss/127031/C%2B%2BJavaPython-Sort-and-Two-pointer

https://leetcode.com/problems/most-profit-assigning-work/discuss/126988/O(M-%2B-N)-solution-based-on-preprocessing

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation