C++でブロック構築にかかる最小時間を求めるアルゴリズム

ブロックのリストがあるとします。blocks[i] = t の場合、i 番目のブロックを構築するには t 単位の時間が必要です。1つのブロックは、必ずちょうど1人の作業員だけが担当できます。各作業員は「2人の作業員に分割する」か「ブロックを1つ構築して退場する」のいずれかの行動を選択でき、それぞれの決断には一定の時間がかかります。作業員を2人に分割するときのコストは、split という数値として与えられます。

問題例

たとえば、blocks = [1, 2]、split = 5 という入力の場合、出力は 7 になります。これは、まず 5 単位の時間をかけて作業員を2人に分割し、それぞれにブロックを1つずつ割り当てることで、合計コストが 5 + max(1, 2) = 7 となるためです。

解法のアプローチ

この問題は、ハフマン符号化とよく似た貪欲法（グリーディー）で効率よく解けます。ポイントは、常に最も小さい2つの値を組み合わせていくことです。具体的な手順は以下の通りです。

• 最小ヒープ（昇順の優先度付きキュー）pq を用意します

• i := 0 から始めて、i が blocks のサイズ未満である間、i を1ずつ増やしながら次を実行します

  • blocks[i] を pq に挿入します

• pq のサイズが1より大きい間、次を繰り返します

  • pq から最小の要素を取り出します

  • x := pq の先頭（次に小さい）要素とし、pq から削除します

  • split + x を pq に挿入します

• pq の先頭要素を答えとして返します

このアルゴリズムが正しく動作する理由は、作業員の分割が二分木の構造をなすためです。構築時間の短いブロックほど深い位置（多くの分割を経由した位置）に置いても全体への影響が小さいため、常に小さい方から統合していくのが最適となります。

それでは、理解を深めるために以下の実装例を見てみましょう。

C++実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minBuildTime(vector<int>& blocks, int split) {
      priority_queue<int, vector<int>, greater<int> > pq;
      for (int i = 0; i < blocks.size(); i++)
      pq.push(blocks[i]);
      while (pq.size() > 1) {
         pq.pop();
         int x = pq.top();
         pq.pop();
         pq.push(split + x);
      }
      return pq.top();
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2};
   cout << (ob.minBuildTime(v, 5));
}

入力

{1,2}, 5

出力

7