LEETCODE JUNE 2021 DAILY CODING CHALLENGE

 LEETCODE JUNE 2021 DAILY CODING CHALLENGE

JUNE 1

JUNE 2

JUNE 3

JUNE 4

JUNE 5

Maximum Performance of a Team

LINK

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 109 + 7.

 

const int mod = 1e9 + 7;

    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {

        vector<pair<int, int>>ord;

        

        for(int i = 0; i < n; i++){

            ord.push_back({efficiency[i], speed[i]});

        }

        sort(ord.rbegin(), ord.rend());

        priority_queue<int>speedPq;

        

        long totalSpeed = 0, res = 0;

        

        for(auto& p : ord){

            int spd = p.second;

            speedPq.push(-spd);

            if(speedPq.size() <= k)

                totalSpeed += spd;

            else{

                totalSpeed += spd + speedPq.top();

                speedPq.pop();

            }

            res = max(res, totalSpeed*p.first);

        }

        return res% mod;

    }