1383. Maximum Performance of a Team

June 5, 2021 - 2 minutes read - 698 words

Leetcode 1383. Maximum Performance of a Team

題目

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

想法

團隊的 efficiency 是團隊中最低的 efficiency。

所以我們可以利用這個特點，先依 efficiency 遞減排序。

遍歷的時候，團隊中最低的 efficiency 就會是當前遍歷到的 efficiency。

那我們接著就只要處理總速度的部分就好了。

用 Min Priority Queue 儲存最快的至多 k 個速度，同時用另一個變數存總速度。

遍歷時，確保 Min Priority Queue 的長度及隨時維護總速度。

如果 Min Priority Queue 的長度超過 k 就刪除最慢的那個。

每次遍歷都會得到一個 performance，最後輸出其中最大的取模 10⁹ + 7。

這題有一些地方要注意：
需用快速的方法維護團隊總速度，使用 Priority Queue
可能出現的超大整數，使用 BigInt
其中 Priority Queue 不用自己寫，Leetcode 的環境本來就有內建了。
然後 BigInt 也是 Javascript 的內建物件。
所以說，實際要寫的其實不多。
當然，也可以自己寫優化的 Min Priority Queue 來加快執行速度。

實作

Javascript

var maxPerformance = function (n, speed, efficiency, k) {
    // 把 engineers 依照 efficiency 遞減排序
    let engineers = [];
    for (let i = 0; i < n; i++) {
        engineers.push({ speed: speed[i], efficiency: efficiency[i] });
    }
    engineers.sort((a, b) => b.efficiency - a.efficiency);

    // 開一個 Priority Queue 存最快的至多 k 個 speed
    let highest_speeds = new MinPriorityQueue();

    // performance 是乘起來的，可能會超過 2^53 ，所以用 BigInt 存
    let max_performance = BigInt(0),
        team_speed = 0;
    
    // 我們從 efficiency 最高的 engineer 往下遍歷
    for (let i = 0; i < n; i++) {
        // 將現在這個的速度存入 Priority Queue
        highest_speeds.enqueue(engineers[i].speed);

        // 也把現在這個的速度加入總速度中
        team_speed += engineers[i].speed;

        // 如果總速度是由多於 k 個速度組成，排除最低速度
        if (highest_speeds.size() > k) {
            team_speed -= highest_speeds.dequeue().element;
        }

        // 計算現在這個 team 的 performance
        // 當前 team 的最低 efficiency 就是現在這個 engineer 的 efficiency
        let performance = BigInt(engineers[i].efficiency) * BigInt(team_speed);

        // 試著更新 max performance
        max_performance = performance > max_performance ? performance : max_performance;
    }

    // 輸出 max performance，記得要取模
    return max_performance % BigInt(1e9 + 7);
};