C++で複数のリストから選んだ要素間の最小差を求めるプログラム

複数のリスト（リストのリスト）が与えられたとき、それぞれのリストから1つずつ値を選び、選ばれた要素の中の最大値と最小値の差をできるだけ小さくする問題を考えます。

例えば、入力が lists = [[30, 50, 90], [85], [35, 70]] の場合、90、85、70 を選ぶと 90 − 70 = 20 となるため、答えは 20 になります。

この問題は、いわゆる「K個のリストをカバーする最小レンジ」問題と同様の考え方で解くことができます。各リストをソートした上で、最小ヒープ（優先度付きキュー）を使い、常に現在の最小値を追跡しながら、現在の最大値との差を順次評価していきます。

アルゴリズムのステップ

この問題を解くために、以下の手順に従います。

• maxVal を −∞（負の無限大）で初期化します。
• 答えとなる ret を ∞（無限大）で初期化します。
• 優先度付きキュー pq を定義します。
• n をリストの数とします。
• i を 0 から n 未満まで1ずつ増やしながら、以下を繰り返します。
  • lists[i] をソートします。
  • {lists[i][0], i, 0}（値、リストのインデックス、要素のインデックス）を pq に挿入します。
  • maxVal を lists[i][0] と maxVal の最大値に更新します。
• pq のサイズが n と等しい間、以下を繰り返します。
  • pq の先頭要素を temp として取り出し、pq から削除します。
  • ret を ret と (maxVal − temp[0]) の最小値に更新します。
  • temp の最後の要素（要素のインデックス）を1増やします。
  • temp の最後の要素が lists[temp[1]] のサイズ未満である場合は、以下を行います。
    • maxVal を maxVal と lists[temp[1]][temp の最後の要素] の最大値に更新します。
    • temp[0] を lists[temp[1]][temp の最後の要素] に設定します。
    • temp を pq に戻します。
• ret を返します。

このアルゴリズムでは、ヒープから最小値を取り出すたびに現在のレンジ（maxVal − 最小値）を計算し、そのリストの次の要素へとポインタを進めることで、すべての選び方の中から最小の差を効率的に見つけることができます。

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
struct Cmp {
   bool operator()(vector<int>& a, vector<int>& b) {
      return !(a[0] < b[0]);
   }
};
class Solution {
   public:
   int solve(vector<vector<int>>& lists) {
      int maxVal = INT_MIN;
      int ret = INT_MAX;
      priority_queue<vector<int>, vector<vector<int>>, Cmp> pq;
      int n = lists.size();
      for (int i = 0; i < n; i++) {
         sort(lists[i].begin(), lists[i].end());
         pq.push({lists[i][0], i, 0});
         maxVal = max(lists[i][0], maxVal);
      }
      while (pq.size() == n) {
         vector<int> temp = pq.top();
         pq.pop();
         ret = min(ret, maxVal - temp[0]);
         temp.back()++;
         if (temp.back() < lists[temp[1]].size()) {
            maxVal = max(maxVal, lists[temp[1]][temp.back()]);
            temp[0] = lists[temp[1]][temp.back()];
            pq.push(temp);
         }
      }
      return ret;
   }
};
int solve(vector<vector<int>>& lists) {
   return (new Solution())->solve(lists);
}
int main(){
   vector<vector<int>> v = {{30, 50, 90},{85},{35, 70}};
   cout << solve(v);
}

入力

{{30, 50, 90},{85},{35, 70}}

出力

20