# 1383. Maximum Performance of a Team
###### tags: `Leetcode` `Hard` `Priority Queue` `Greedy`
Link: https://leetcode.com/problems/maximum-performance-of-a-team/
## 思路 $O(NlogN)$ $O(N)$
#### Intuition
和[0857. Minimum Cost to Hire K Workers](https://hackmd.io/Ssaze_deSyi6x6qnHjWwHw)很像
两个变量speed和efficiency
先fix住一个efficiency，For each candidate, we treat him/her as the one who has the minimum efficiency in a team. Then, we select the rest of the team members based on this condition.
那么我们应该是遍历一遍array, 找到所有efficiency比他高的，然后用pq去除掉多余k的那些engineer, 也就是我们把pq里面的engineer按照speed大小从小到大排，当pq size大于k，就poll()
最直觉的做法就是遍历一遍所有efficiency的可能值，然后求出答案
更简单的方法就是我们先把engineer array按照efficiency排序 保证它在遍历的过程中 前面放进pq的一定都是efficiency大于或等于现在的engineer的efficiency的 这样就能降低时间复杂度
## Code

class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        ans = 0
        currSpeedSum = 0
        pq = []
        for s, e in sorted(list(zip(speed, efficiency)), key = lambda ab:-ab[1]):
            heappush(pq, s)
            currSpeedSum += s
            if len(pq)>k:
                currSpeedSum -= heapq.heappop(pq)
            ans = max(ans, currSpeedSum*e)
        return ans%(10**9+7)

class Solution {
    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        //0 efficiency //1 speed
        int[][] engineers = new int[speed.length][2];
        for(int i=0; i<speed.length; i++){
            engineers[i] = new int[]{efficiency[i], speed[i]};
        }
        Arrays.sort(engineers, (a,b)->(b[0]-a[0]));
        
        PriorityQueue<Integer> pq = new PriorityQueue<>(k, (a, b) -> a - b);
        long res = Long.MIN_VALUE, total_speed = 0;
        for(int[] engineer:engineers){
            if(pq.size()==k) total_speed -= pq.poll();
            total_speed += engineer[1];
            res = Math.max(res, (total_speed*engineer[0]));
            pq.add(engineer[1]);
        }
        
        return (int)(res%1000000007);
    }
}