Maximum Performance of a Team: ประสิทธิภาพสูงสุดของทีมใน C++

ปัญหา

มีวิศวกร n คน แต่ละคนมี speed[i] และ efficiency[i] เลือกทีมสูงสุด k คน เพื่อให้ Performance = (Sum of speeds) × (Min efficiency) สูงสุด คำตอบ modulo 10^9 + 7

ตัวอย่าง: n=6, speed=[1,5,8,2,10,3], efficiency=[9,7,2,5,4,3], k=2 → เลือกวิศวกร speed=10,eff=4 และ speed=5,eff=7 → (10+5) × min(4,7) = 60

แนวคิด: Greedy + Priority Queue

ข้อสังเกต

ถ้ารู้ Min Efficiency = e ของทีม แล้ว เราควรเลือกวิศวกรที่มี efficiency ≥ e และ speed สูงสุด k คน

อัลกอริทึม

1. จับคู่ (efficiency, speed) และ เรียงตาม efficiency จากมากไปน้อย
2. วนตามลำดับ efficiency (ค่าที่กำลังพิจารณาเป็น Min Efficiency ของทีม)
3. Maintain Min-Heap ของ Speed ขนาดสูงสุด k:
   • Push speed ปัจจุบันเข้า heap
   • ถ้า heap size > k: pop speed น้อยสุดออก (เพื่อเก็บ speed สูงสุด k ค่า)
   • คำนวณ current_sum_speed × current_efficiency
4. เก็บค่าสูงสุด

โค้ด C++

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

class Solution {
public:
    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
        vector<pair<int, int>> engineers;
        for (int i = 0; i < n; i++) {
            engineers.emplace_back(efficiency[i], speed[i]);
        }
        
        // เรียง efficiency จากมากไปน้อย
        sort(engineers.rbegin(), engineers.rend());
        
        // Min-heap เก็บ speed สูงสุด k ค่า
        priority_queue<int, vector<int>, greater<int>> pq;
        long long sum_speed = 0;
        long long ans = 0;
        const long long MOD = 1e9 + 7;
        
        for (auto& [eff, spd] : engineers) {
            if (pq.size() == k) {
                sum_speed -= pq.top();
                pq.pop();
            }
            pq.push(spd);
            sum_speed += spd;
            ans = max(ans, sum_speed * eff);
        }
        
        return ans % MOD;
    }
};

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

การเดินตัวอย่าง

ความซับซ้อน

• Time: O(n log n) (Sorting + Heap operations)
• Space: O(n) สำหรับ sorting + O(k) สำหรับ heap

Input / Output

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