C++で解く「最小給油回数」問題 ― 貪欲法と優先度付きキューを使った効率的な解法

問題の概要

ある車が出発地点から出発し、東に t マイル離れた目的地まで走行することを考えます。道中には複数のガソリンスタンドが点在しており、各 station[i] は「出発地点から東に station[i][0] マイルの位置にあり、station[i][1] リットルの燃料を備えたスタンド」を表します。

車の燃料タンクの容量は無限で、出発時には startFuel リットルの燃料が入っています。車は 1 マイル走行するごとに 1 リットルの燃料を消費します。

車はガソリンスタンドに到達すると、そこで立ち寄って給油することができ、そのスタンドの燃料をすべてタンクに移し替えられます。目的地に到達するために必要な給油(立ち寄り)の最小回数を求めてください。どうしても目的地に到達できない場合は -1 を返します。

具体例で確認する

たとえば、Target = 100、startFuel = 10、stations = [[10,40],[20,30],[30,20],[60,40]] という入力の場合、出力は 3 になります。動きを順に追ってみましょう。

• 出発時: 燃料は 10 リットルあるため、位置 10 マイルのスタンドまで到達できます。
• 1回目の給油: 位置 10 のスタンドで 40 リットルを受け取り、到達可能距離は 10 + 40 = 50 マイルに伸びます。
• 2回目の給油: 位置 50 マイル以内には [20,30] と [30,20] の2つのスタンドがあります。通過済みのスタンドのうち最も燃料の多い 30 リットルを選んで給油すると、到達可能距離は 50 + 30 = 80 マイルになります。
• 3回目の給油: 位置 80 マイル以内には [60,40] も含まれます。残りの候補から最大の 40 リットルを給油すると、到達可能距離は 80 + 40 = 120 マイルとなり、目的地の 100 マイルを余裕をもって超えられます。

以上より、必要な給油回数は 3 回です。

解法のアプローチ

この問題は、貪欲法と優先度付きキュー(最大ヒープ)を組み合わせることで効率的に解けます。基本となる考え方は次のとおりです。

「現時点で到達可能な範囲にあるスタンドをすべて記録しておき、燃料が足りなくなった時点で、その中から最も燃料の多いスタンドを選んで給油する」

この戦略により、給油のたびに到達可能距離を最大限に伸ばすことができ、結果として最小の給油回数が保証されます。

アルゴリズムの手順

• curr := 0(到達可能な最大距離)とする
• スタンドの配列 st を位置の昇順にソートする
• 最大ヒープとして機能する優先度付きキュー pq を用意する
• i := 0、cnt := 0 と初期化する
• curr に初期燃料 fuel を加算する
• curr < target の間、次の処理を繰り返す:
  • cnt を 1 増やす
  • i が st のサイズ未満 かつ st[i][0] <= curr の間、st[i][1] を pq に挿入し、i を 1 増やす
  • pq が空であれば、ループを抜ける(これ以上進めない)
  • curr に pq の先頭要素(最大値)を加算し、pq からその要素を削除する
• curr >= target であれば cnt を、そうでなければ -1 を返す

計算量

スタンドの数を N とすると、ソートに O(N log N)、各スタンドのヒープへの挿入・削除にも全体で O(N log N) かかるため、時間計算量は O(N log N) です。空間計算量は O(N) です。

C++での実装例

以下に実装を示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int minRefuelStops(int target, int fuel, vector<vector<int>> &st) {
        int curr = 0;
        sort(st.begin(), st.end());
        priority_queue<int> pq;
        int i = 0;
        int cnt = 0;
        curr += fuel;
        while (curr < target) {
            cnt++;
            while (i < st.size() && st[i][0] <= curr) {
                pq.push(st[i][1]);
                i++;
            }
            if (pq.empty())
                break;
            curr += pq.top();
            pq.pop();
        }
        return curr >= target ? cnt : -1;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{10,40},{20,30},{30,20},{60,40}};
    cout << (ob.minRefuelStops(100, 10, v));
}

入力

100, 10, {{10,40},{20,30},{30,20},{60,40}}

出力

3

まとめ

最小給油回数問題は、「到達可能なスタンドの中から最も燃料の多いものを選ぶ」という貪欲戦略と優先度付きキューを組み合わせることで、O(N log N) の計算量で解くことができます。進みながら選択肢を蓄積し、必要になった時点で最善の選択を行うというパターンは、他の貪欲法の問題にも応用できる重要なテクニックです。