C++でチームの最大パフォーマンスを求めるアルゴリズム

問題の概要

n人のエンジニアがいるとします。彼らには1からnまでの番号が振られており、2つの配列 speed と efficiency が与えられます。speed[i] と efficiency[i] は、それぞれi番目のエンジニアの作業速度と効率を表します。

このとき、最大k人のエンジニアで構成されるチームの最大パフォーマンスを求める必要があります。答えは非常に大きな値になる可能性があるため、10⁹ + 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) = 15 × 4 = 60

解法のアプローチ

この問題は、貪欲法と優先度付きキュー（ヒープ）を組み合わせることで効率的に解くことができます。ポイントは次の2点です。

• 効率の降順でエンジニアをソートする：これにより、あるエンジニアを処理している時点では、まだ処理していないエンジニアの効率は必ずそのエンジニア以下になります。つまり、現在処理中のエンジニアの効率が「候補チーム全体の最小効率」として確定します。
• 最小ヒープで上位k人の速度を管理する：ヒープのサイズがkに達したら、最も遅いエンジニアを取り除くことで、常に合計速度を最大化します。

アルゴリズムの手順

1. 答えを格納する変数 ret を0で初期化します。
2. {efficiency, speed} のペアを格納する2次元配列 v を作成します。
3. v を降順にソートします。
4. 最小ヒープとして優先度付きキュー pq を用意し、合計速度 sum を0で初期化します。
5. i = 0 から n-1 まで以下を繰り返します。
   • pq のサイズが k と等しい場合、sum から pq の先頭（最小の速度）を引いて削除します。
   • sum に v[i] の速度を加算し、pq にも追加します。
   • ret を max(ret, sum × v[i] の効率) で更新します。
6. ret を 10⁹ + 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);
   }
};
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));
}

入力

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

出力

60

計算量の評価

ソートに O(n log n)、各エンジニアごとにヒープ操作が O(log k) 発生するため、全体の時間計算量は O(n log n) となります。空間計算量は、ペア配列とヒープの分だけ必要なので O(n) です。

また、合計速度と効率の積は簡単に32ビット整数の範囲を超えるため、long long int を使ってオーバーフローを防いでいる点にも注意しましょう。