# [LeetCode 1383. Maximum Performance of a Team ](https://leetcode.com/explore/challenge/card/june-leetcoding-challenge-2021/603/week-1-june-1st-june-7th/3768/)
### Daily challenge Jun 5, 2021 (HARD)

:::success
[相似題 : 857. Minimum Cost to Hire K Workers](https://hackmd.io/TsqkcrqrS2-tIhEQXIYM0A)
:::

>You are given two integers **`n`** and **`k`** and two integer arrays **`speed`** and **`efficiency`** both of length n. There are **`n engineers`** numbered from 1 to n. **`speed[i]`** and **`efficiency[i]`** represent the speed and efficiency of the ith engineer respectively.
>
>Choose **`at most k`** different engineers out of the **`n`** engineers to form a team with the maximum **`performance`**.
>
>The performance of a team is the sum of their engineers' speeds multiplied by the minimum efficiency among their engineers.
>
>Return the maximum performance of this team. Since the answer can be a huge number, return it **modulo** 10^9^ + 7.

:::info
**Example 1:**
**Input:** n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
**Output:** 60
**Explanation:**
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.
:::

:::info
**Example 2:**
**Input:** n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
**Output:** 68
**Explanation:**
This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.
:::

:::info
**Example 3:**
**Input:** n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
**Output:** 72
:::

:::warning
**Constraints:**
* 1 <= k <= n <= 105
* speed.length == n
* efficiency.length == n
* 1 <= speed[i] <= 105
* 1 <= efficiency[i] <= 108
:::

---

### Approach 1 : Min Heap ( Priority Queue ) :book:
**`80 ms ( 77.75% )`** **`O()`**

* 將 `speed & efficiency` 存入 **`pair`** 中，並將 `efficiency` 的部分`由大到小`進行 **`sort`**。
* **`SumOfSpeed`** 紀錄當前 `speed` 總和， **`ans`** 紀錄當前最大答案。
* 目標找出最大的 **`performance = SumOfSpeed * efficiency[i]`** ( 因為 `sort` 後， `efficiency[i] <= efficiency[i-1]`，所以計算時只需考慮 `SumOfSpeed` 以及 `efficiency[i]` )。
* **`min_heap`** 紀錄目前使用的 `speed`，
>* 每次都將 `speed[i]` 放入 `heap` 中，**`SumOfSpeed += speed[i]`**。
>* 當 `size > k` 時，**`SumOfSpeed -= heap.top()`**，並 `pop top of the value`。
>* 判斷最大值 **`ans = max(ans, performance = SumOfSpeed * efficiency[i])`**。
---
>**EXAMPLE :**
>**`speed = [2, 10, 3, 1, 5, 8]`、`efficiency = [5, 4, 3, 9, 7, 2]`、`k = 2`**。
> 1. **sort efficiency** :
> ---> `s = [1, 5, 2, 10, 3, 8]`。
> ---> `e = [9, 7, 5, 4, 3, 2]`。
> 2. **Min Heap** :
> **`SumOfSpeed = 0`**、**`ans = 0`**。
>> * i = 0 ---> heap = `({1, 9})`。
>> **`SumOfSpeed = 1`**、**`performance = 1 * 9 = 9`**、**`ans = 9`** :+1: 。
>> * i = 1 ---> heap = `({1, 9}, {5, 7})`。
>> **`SumOfSpeed = 6`**、**`performance = 6 * 7 = 42`**、**`ans = 42`** :+1: 。
>> * i = 2 ---> heap = `({2, 5}, {5, 7})`。
>> **`SumOfSpeed = 7`**、**`performance = 7 * 5 = 35`**、**`ans = 42`** :-1:。
>> * i = 3 ---> heap = `({10, 4}, {5, 7})`。
>> **`SumOfSpeed = 15`**、**`performance = 15 * 4 = 60`**、**`ans = 60`** :+1:。
>> * i = 4 ---> heap = `({10, 4}, {5, 7})`。 ( `{3, 3}` is impossible to be a good answer, becuase its `speed & efficiency` are both small。)
>> * i = 5 ---> heap = `({10, 4}, {8, 2})`。
>> **`SumOfSpeed = 18`**、**`performance = 18 * 2 = 36`**、**`ans = 60`** :-1:。

class Solution {
public:
    #define MOD 1000000007
    
    static bool cmp(pair<int, int> a, pair<int, int> b){
        return a.second > b.second;
    }
    
    
    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
        vector<pair<int, int> > people;
        priority_queue<int, vector<int>, greater<int> > heap;   // stroe speed
        
        for(int i=0; i<n; i++){
            people.push_back({speed[i], efficiency[i]});
        }
        sort(people.begin(), people.end(), cmp);    // sort by efficiency
        
        long long int SumOfSpeed = 0;
        long long int ans = 0;
        for(int i=0; i<n; i++){
            heap.push(people[i].first);
            SumOfSpeed += people[i].first;
            
            if(heap.size() > k){
                SumOfSpeed -= heap.top();
                heap.pop();
            }
              
            ans = max(ans, SumOfSpeed * people[i].second);
        }
        
        return ans % MOD;
    }
};