# Leetcode [No. 826] Most Profit Assigning Work (MEDIUM) 解題心得

## 題目

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

## 思路
+ 這個解法是先用一個data structure來把difficult跟profit存成一個struct，接著只對profit去做sorting，做完以後可以用greedy下去搜，就從最後面開始看profit最高的這個worker是否可以負擔這個difficulty，不行的話就往前一個看。

class Solution {
public:
    // create a data structure including diffculty and profit.
    struct job{
        int difficulty;
        int profit;
    };

    // 定义一个比较函数，只根据利润进行排序
    static bool cmp(const job &a, const job &b) {
        return a.profit < b.profit;
    }

    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        int maxProfit = 0;
        vector<job> jobs(difficulty.size());
        for(int i = 0 ; i < jobs.size(); i++)
        {
            jobs[i].difficulty = difficulty[i];
            jobs[i].profit = profit[i];
        }
        sort(jobs.begin(), jobs.end(), cmp);
        for (int i = 0 ; i < worker.size(); i++)
        {
            for(int j = jobs.size()-1; j >= 0; j--)
            {
                if(worker[i]>= jobs[j].difficulty)
                {
                    maxProfit += jobs[j].profit;
                    break;
                }
            }
        }
        return maxProfit;
    }
};

### 解法分析
+ time complexity: O(n^2)

### 執行結果


## 改善:

+ 把j記住，這樣就不會每次都從最後一個找了

class Solution {
public:
    // create a data structure including diffculty and profit.
    struct job{
        int difficulty;
        int profit;
    };

    // 定义一个比较函数，只根据利润进行排序
    static bool cmp(const job &a, const job &b) {
        return a.profit < b.profit;
    }

    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        int maxProfit = 0;
        vector<job> jobs(difficulty.size());
        for(int i = 0 ; i < jobs.size(); i++)
        {
            jobs[i].difficulty = difficulty[i];
            jobs[i].profit = profit[i];
        }
        sort(jobs.begin(), jobs.end(), cmp);
        sort(worker.begin(),worker.end(), greater<int>()); //sort worker from big to small
        for (int i = 0, j = jobs.size()-1; i < worker.size(); i++)
        {
            while(j>=0 && worker[i]<jobs[j].difficulty)
            {
                j--;
            }
            if(j>=0)
                maxProfit += jobs[j].profit;
        }
        return maxProfit;
    }
};

### 解法分析
+ time complexity: O(nlgn)

### 執行結果