C++ में टीम का अधिकतम प्रदर्शन

समस्या विवरण

मान लीजिए n इंजीनियर हैं। उन्हें 1 से n तक नंबर दिया गया है और हमारे पास दो सरणियाँ हैं: speed और efficiency, यहां speed[i] और efficiency[i] i-वें इंजीनियर की गति और दक्षता को दर्शाते हैं। हमें अधिकतम k इंजीनियरों से बनी टीम का अधिकतम प्रदर्शन ज्ञात करना है। उत्तर बहुत बड़ा हो सकता है इसलिए इसे 10^9 + 7 से मॉड्यूलो करके लौटाएं।

यहां एक टीम का प्रदर्शन उनके इंजीनियरों की गति के योग को उनकी न्यूनतम दक्षता से गुणा करके प्राप्त होता है।

उदाहरण

यदि इनपुट है: n = 6, speed = [1,5,8,2,10,3], efficiency = [9,7,2,5,4,3], k = 2, तो आउटपुट होगा 60, क्योंकि टीम का अधिकतम प्रदर्शन गति 10 और दक्षता 4 वाले इंजीनियर और गति 5 और दक्षता 7 वाले इंजीनियर को चुनकर प्राप्त होता है। यानी, प्रदर्शन = (10 + 5) * min(4, 7) = 60।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए निम्नलिखित चरणों का पालन करें (लालची + प्रायोरिटी क्यू):

ret := 0
एक 2D सरणी v परिभाषित करें
i := 0 से आरंभ करें, जब i < n, i को 1 से बढ़ाते हुए:
- {e[i], s[i]} को v के अंत में डालें
सरणी v को रिवर्स क्रम में सॉर्ट करें
एक प्रायोरिटी क्यू pq परिभाषित करें
sum := 0
i := 0 से आरंभ करें, जब i < n, i को 1 से बढ़ाते हुए:
- यदि pq का आकार, k के समान है:
  - sum := sum - pq का शीर्ष तत्व
  - pq से तत्व हटाएं
- sum := sum + v[i][1]
- v[i][1] को pq में डालें
- ret := ret और sum * v[i][0] का अधिकतम
ret % (10^9 + 7) लौटाएं

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maxPerformance(int n, vector<int>& s, vector<int>& e, int k) {
        long long int ret = 0;
        vector<vector<int>> v;
        for (int i = 0; i < n; i++) {
            v.push_back({ e[i], s[i] });
        }
        sort(v.rbegin(), v.rend());
        priority_queue<int, vector<int>, greater<int>> pq;
        long long int sum = 0;
        for (int i = 0; i < n; i++) {
            if (pq.size() == k) {
                sum -= pq.top();
                pq.pop();
            }
            sum += v[i][1];
            pq.push(v[i][1]);
            ret = max(ret, sum * v[i][0]);
        }
        return ret % (long long int)(1e9 + 7);
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,5,8,2,10,3};
    vector<int> v1 = {9,7,2,5,4,3};
    cout << (ob.maxPerformance(6, v, v1, 2));
    return 0;
}

इनपुट

6, {1,5,8,2,10,3}, {9,7,2,5,4,3}, 2