C++で解く「最大利益の仕事割り当て」問題 ― ソートと貪欲法による効率的な解法

問題の概要

difficulty[i] は i 番目の仕事の難易度、profit[i] は i 番目の仕事を完了させたときに得られる利益を表します。さらに、worker[i] は i 番目の労働者の能力を表し、この労働者は難易度が worker[i] 以下の仕事しか担当できません。各労働者が担当できる仕事は最大で 1 つですが、同じ仕事を複数人の労働者が担当することは可能です。この条件のもとで、得られる利益の合計の最大値を求めます。

具体例

入力が difficulty = [2,4,6,8,10]、profit = [10,20,30,40,50]、worker = [4,5,6,7] の場合、出力は 100 になります。このとき、労働者にはそれぞれ難易度 [4,4,6,6] の仕事を割り当てることができ、得られる利益は [20,20,30,30]、合計で 100 となります。

アルゴリズムの手順

この問題は、ソートと貪欲法（グリーディ法）を組み合わせることで効率的に解くことができます。手順は以下の通りです。

• 答えを格納する ans を 0、n を profit 配列のサイズとして初期化します
• worker 配列を昇順にソートします
• (難易度, 利益) のペアを格納するリスト v を作成します
• i を 0 から n−1 までループし、ペア (difficulty[i], profit[i]) を v に追加します
• v を昇順にソートします
• maxVal を 0、m を worker 配列のサイズ、j を 0 として初期化します
• i を 0 から m−1 までループします
  • j < n かつ v[j].first <= worker[i] である間、次を繰り返します
    • maxVal を maxVal と v[j].second の大きい方で更新します
    • j を 1 増やします
  • ans に maxVal を加算します
• 最後に ans を返します

このアルゴリズムのポイントは、maxVal が「それまでに確認した仕事のうち、現在の労働者が対応できる範囲での最大利益」を保持し続ける点です。労働者を能力の昇順に処理していくため、前の労働者の段階で更新された maxVal をそのまま再利用でき、二度同じ仕事を見直す必要がありません。

C++ 実装例

以下に、上記のアルゴリズムを実装した C++ コードを示します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
      int ans = 0;
      sort(worker.begin(), worker.end()); // 労働者を能力の昇順にソート
      vector < pair <int, int> > v;
      int n = profit.size(); // 仕事の数
      for(int i = 0; i < n; i++){
         v.push_back({difficulty[i], profit[i]});
      }
      sort(v.begin(), v.end()); // 難易度の昇順にソート
      int maxVal = 0;
      int m = worker.size(); // 労働者の数
      int j = 0;
      for(int i = 0; i < m; i++){
         while(j < n && v[j].first <= worker[i]){
            maxVal = max(maxVal, v[j].second);
            j++;
         }
         ans += maxVal;
      }
      return ans;
   }
};
int main() {
   Solution ob1;
   vector<int> difficulty{2,4,6,8,10};
   vector<int> profit{10,20,30,40,50};
   vector<int> worker{4,5,6,7};
   cout << ob1.maxProfitAssignment(difficulty, profit, worker) << endl;
   return 0;
}

入力

difficulty = {2,4,6,8,10}
profit = {10,20,30,40,50}
worker = {4,5,6,7}

出力

100

計算量

時間計算量は O(n log n + m log m) です（n は仕事の数、m は労働者の数）。これは主にソートのコストが支配的であるためです。その後の貪欲法による走査は線形時間で完了します。空間計算量は、(難易度, 利益) のペアを格納するため O(n) となります。全探索（O(n × m)）に比べて大幅に高速であり、大規模な入力にも対応できる実用的な解法です。