LeetCode 826 - Most Profit Assigning Work

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

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]

X. Two Pointers
Solution 1: Sort and two pointers

那么一个方法就是对于<difficulty, profit>这个pair进行排序，按照difficulty为index升序排列。

同时对于worker也升序排序。

这样两个都排序完后，就可以对于每个worker，找到所有difficulty < worker的job，看看哪个job能获得最大的利润就把这个job分配给当前的worker。

这里有2个关键的问题，(1)为什么要从最小的worker开始? (2)为什么要对于每个worker分配job，而不是为每个job寻找一个worker?

1. 这是因为最小的worker是最不容易满足的，而job充足的情况下worker是不应该被浪费的，否则利润一定不是最大
2. 给worker找job是因为worker不应该被浪费的，因为如果一个job没有被分配，可能不会影响全局的任务，但如果有worker没有任务，一定会影响全局的总利润(worker大于job的情况，或者本来就无法全部分配的情况除外)

这样一来就比较清晰了，还有一个需要注意的点就是如何写代码，特别是C++不像python一样能方便的实现pair的sort(其实也可以, sort有这个功能，只不过需要新复制构造一个pair的vector)

时间的复杂度官方说是$O(NlogN+QlogQ)$, 其中$N$是job的数量，$Q$是worker的数量。这是因为虽然对于每个worker找job的过程看起来是个NQ的过程，但是由于已经排过序了，所以可以用two-pointer的方法将复杂度降到$O(N+Q)$, 个人觉得这是一个值得记的点，就是对于已经排序的序列，可以尽可能的利用二分、two-pointer这种优化。

贪心（Greedy Algorithm）

每个工人都选择不大于其难度上限的最大收益的任务

问题即转化为求范围内的最大值

We can consider the workers in any order, so let's process them in order of skill.

If we processed all jobs with lower skill first, then the profit is just the most profitable job we have seen so far.

Algorithm

We can use a "two pointer" approach to process jobs in order. We will keep track of best, the maximum profit seen.

For each worker with a certain skill, after processing all jobs with lower or equal difficulty, we add best to our answer.

• Time Complexity: $O(N \log N + Q \log Q)$, where $N$ is the number of jobs, and $Q$ is the number of people.
• Space Complexity: $O(N)$, the additional space used by jobs.

    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        int N = difficulty.length;
        Point[] jobs = new Point[N];
        for (int i = 0; i < N; ++i)
            jobs[i] = new Point(difficulty[i], profit[i]);
        Arrays.sort(jobs, (a, b) -> a.x - b.x);
        Arrays.sort(worker);

        int ans = 0, i = 0, best = 0;
        for (int skill: worker) {
            while (i < N && skill >= jobs[i].x)
                best = Math.max(best, jobs[i++].y);
            ans += best;
        }

        return ans;
    }
https://leetcode.com/problems/most-profit-assigning-work/discuss/127031/C++JavaPython-Sort-and-Two-pointer

1. zip difficulty and profit as jobs.
2. sort jobs and sort 'worker'.
3. 2 pointers idea, for each worker, find his maximum profit he can make under his ability.
   Because we have sorted jobs and worker, we will go through two lists only once.
   It will be only O(M+N).

Time Complexity
O(NlogN + MlogM), as we sort list.

    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        List<Pair<Integer, Integer>> jobs = new ArrayList<>();
        int N = profit.length, res = 0, i = 0, maxp = 0;
        for (int j = 0; j < N; ++j) jobs.add(new Pair<Integer, Integer>(difficulty[j], profit[j]));
        Collections.sort(jobs, Comparator.comparing(Pair::getKey));
        Arrays.sort(worker);
        for (int ability : worker) {
            while (i < N && ability >= jobs.get(i).getKey())
                maxp = Math.max(jobs.get(i++).getValue(), maxp);
            res += maxp;
        }
        return res;
    }

X. Bucket Sort
https://marcelarthur.github.io/LeetCode每日三题pickone-826-Most-Profit-Assigning-Work/
借鉴桶排序的的思想,首先分配一个数组d[100001]代表每个difficulty的最大profit，先初始化值，然后从前到后扫一遍，确保每个d[i]放的的确是difficulty为i时的最大利润
https://zihan.me/2018/04/23/LeetCode-826-Most-Profit-Assigning-Work/#Solution-1-Sort-and-two-pointers

    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        memset(cnt, 0, sizeof(cnt));
        int dsize = difficulty.size(), wsize = worker.size(), res = 0;
        for (int i = 0; i < dsize; ++i) {
            cnt[difficulty[i]] = (profit[i] > cnt[difficulty[i]] ? profit[i] : cnt[difficulty[i]]);
        }
        for (int i = 1; i <= 100000; ++i) {
            cnt[i] = (cnt[i] < cnt[i - 1] ? cnt[i - 1] : cnt[i]);
        }
        // then just sum all the expected profit of each worker in corresponding diffculty
        for (int i = 0; i < wsize; ++i) {
            res += cnt[worker[i]];
        }
        return res;
    }
private:
    int cnt[100001]; // the range is from [1, 100000]

https://zxi.mytechroad.com/blog/greedy/leetcode-826-most-profit-assigning-work/
Solution 2: Bucket + Greedy

Key idea: for each difficulty D, find the most profit job whose requirement is <= D.

Three steps:

1. for each difficulty D, find the most profit job whose requirement is == D, best[D] = max{profit of difficulty D}.
2. if difficulty D – 1 can make more profit than difficulty D, best[D] = max(best[D], best[D – 1]).
3. The max profit each worker at skill level D can make is best[D].

Time complexity: O(n)

Space complexity: O(10000)

  int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {

    const int N = 100000;

    // max profit at difficulty i

    vector<int> max_profit(N + 1, 0);

    for (int i = 0; i < difficulty.size(); ++i)

      max_profit[difficulty[i]] = max(max_profit[difficulty[i]], profit[i]);

    for (int i = 2; i <= N; ++i)

      max_profit[i] = max(max_profit[i], max_profit[i - 1]);

    int ans = 0;

    for (int level : worker)

      ans += max_profit[level];

    return ans;

  }

  int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {

    map<int, int> bests;

    for (int i = 0; i < difficulty.size(); ++i)

      bests[difficulty[i]] = max(bests[difficulty[i]], profit[i]);

    int best = 0;

    for (auto it = bests.begin(); it != bests.end(); ++it)

      it->second = best = max(it->second, best);    

    int ans = 0;

    for (int level : worker)

      ans += prev(bests.upper_bound(level))->second;

    return ans;

  }

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

public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
       
        TreeMap<Integer, Integer> tmap = new TreeMap<>();
        for (int i = 0; i < difficulty.length; i++) {
            tmap.put(difficulty[i], Math.max(profit[i], tmap.getOrDefault(difficulty[i], 0)));
        }

        int max = 0, res = 0;
        for (Integer key : tmap.keySet()) {
            max = Math.max(tmap.get(key), max);
            tmap.put(key, max);
        }
        
        Map.Entry<Integer, Integer> entry = null;
        for (int i = 0; i < worker.length; i++) {
            entry = tmap.floorEntry(worker[i]);            
            if (entry != null) {
                res += entry.getValue();
            }  
        }
        return res;  
}

X. PriorityQueue
https://leetcode.com/problems/most-profit-assigning-work/discuss/126955/Extremely-Simple-Using-Priority-Queue

Sort the class Work in ascending order of difficulty. If difficulty is the same, sort according to descending order of profit. Sort the worker as per ascending order of their ability.

Now you just need to match the work with the worker and store the max profit seen until now and add it to the total profit.

    class Work{
        int d; 
        int p; 
        Work(int d, int p){
            this.d = d; 
            this.p = p; 
        }
    }
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        PriorityQueue<Work> pq = new PriorityQueue<Work>((a, b)->(a.d==b.d)?b.p-a.p:a.d-b.d);
        for(int i = 0; i < profit.length; ++i){
            pq.offer(new Work(difficulty[i], profit[i])); 
        }
        Arrays.sort(worker); 
        int i = 0; 
        int cprofit = 0; 
        int max = 0; 
        while(!pq.isEmpty() && i < worker.length){
            Work w = pq.poll(); 
            if(w.d <= worker[i]){
                max = Math.max(max, w.p); 
            }else{
                i++; 
                cprofit+=max; 
                pq.offer(w); 
            }
        }
        while(i < worker.length){
            cprofit+=max; 
            i++; 
        }
        return cprofit; 
    }

https://zihan.me/2018/04/23/LeetCode-826-Most-Profit-Assigning-Work/#Brute-forcing-way
Brute forcing way

这题比较有趣，一开始最容易想到的当然是$O(n^2)$的算法，对于每个worker，找到difficulty小于它并且profit最大的那个job，但是这样做会超时。

问题就在于这个job是无序的，那么每次寻找的时候就必须使用$O(n)$的遍历时间，非常慢。