コーディング面接：Max Heapを用いた最小給油回数

問題の概要と背景

これはリソース制約のある貪欲法の問題です。燃料はすでに通過したスタンドからのみ補給可能であり、目的は総燃料量ではなく給油回数の最小化です。優れた面接の回答では、到達可能性、遅延決定、Max Heapの不変条件、そして最後のスタンドから目的地までの最終区間を結びつけて説明します。

面接官が見ているポイント

「必要なときだけ給油する」という考え方を遅延貪欲法（lazy greedy strategy）に落とし込めているか。
通過済みのスタンドのうち最大の燃料を選択しても、最適な給油回数が増加しないことを証明できるか。
出発地点、目的地、重複する位置、到達不能なケースを適切に処理できるか。
時間計算量 O(n log n)、空間計算量 O(n) の実装を提示できるか。

質問による前提条件の確認

スタンドが位置順に並んでいるか、重複する位置が許可されているか、燃料が非負であるか、目的地自体がスタンドであるかを確認します。入力サイズと整数の範囲についても尋ねます。デフォルトのモデルでは位置0から開始し、到達した後にのみそのスタンドの燃料を使用できます。

30秒での回答アウトライン

位置順にスタンドを走査し、通過したすべての燃料量をMax Heapに追加します。次のスタンドまたは目的地に到達する前に、移動距離を引きます。燃料が負になった場合は給油が必要になるため、通過した最大燃料を繰り返しpopして給油回数をインクリメントします。ヒープが空になった場合は -1 を返します。強制給油のたびに利用可能な最大燃料を選択することで、給油回数を増やすことなく到達可能距離を最大化できます。

ステップバイステップの解説

1. 到達可能性の不変条件を確立する

位置 p において、ヒープには p 以前のすべてのスタンドの燃料が含まれており、fuel は未使用の量です。燃料が負になった場合、それらのスタンドのいずれかを使用しなければ前進できません。燃料量が再び非負になるまでpopを繰り返すことで、到達可能範囲が拡大します。

2. 遅延貪欲選択の正当性を証明する

給油が必要な際、最適解が通過済みのより小さい燃料量 a を選択し、より大きい燃料量 b が利用可能であると仮定します。a を b に置き換えても、給油回数は変わらず、この時点以降の残燃料は減少しないため、それ以降のすべての区間は実行可能なままです。この交換を繰り返すことで、常に最大値を選択する同等に最適な解が得られます。

3. 目的地を境界として処理する

仮想スタンド (target, 0) を末尾に追加し、他のすべての位置とまったく同じように処理します。位置0から開始し、各距離を減算した後に初めてスタンドの燃料を追加します。目的地で依然としてpopが必要な場合、それらの給油もカウントされます。燃料が負の状態でヒープが空になった場合は、目的地が到達不能であることを意味します。

4. ヒープの実装

Pythonの heapq はMin Heapであるため、負の燃料値を使用してMax Heapをシミュレートします。各スタンドは一度だけpushされ、給油が必要な場合にのみpopされます：

python

import heapq

def min_refuel_stops(target, start_fuel, stations):
    fuel = start_fuel
    previous = 0
    max_heap = []
    stops = 0

    for position, station_fuel in [*stations, (target, 0)]:
        fuel -= position - previous
        while fuel < 0 and max_heap:
            fuel += -heapq.heappop(max_heap)
            stops += 1
        if fuel < 0:
            return -1
        heapq.heappush(max_heap, -station_fuel)
        previous = position
    return stops

5. 計算量と境界条件の分析

n 個のスタンドがある場合、各燃料値はヒープに最大1回入り、最大1回出るため、時間計算量は O(n log n)、ヒープの空間計算量は O(n) になります。十分な初期燃料がある場合、最初のスタンドに到達できない場合、最後のスタンド通過後に給油が必要な場合、燃料が0の場合、重複する位置、目的地へのぴったりな到達、目的地に到達できない場合などをテストします。

模範解答の例

目的地を燃料0の仮想スタンドとして末尾に追加します。走査中は移動距離を減算し、到達済みのスタンドの燃料をヒープにpushします。残燃料が負になるたびに給油が必要となるため、現在位置に到達可能になるまで過去の最大燃料を繰り返し取り出します。ヒープが空になれば -1 を返します。交換証明により、選択されたより小さい通過燃料をより大きい利用可能な燃料に置き換えても、給油回数が増加したり将来の到達可能性が低下したりしないことが示されます。各スタンドのpushとpopは高々1回であるため、計算量は時間 O(n log n)、空間 O(n) となります。

よくあるミス

判断を遅延させず、すべてのスタンドで即座に給油してしまう。
スタンド間のギャップのみをチェックし、目的地までの最終区間を忘れる。
現在の未使用燃料とヒープ内の利用可能な燃料を混同する。
Min Heapを使用して最小量を取り出してしまう。
到達する前にスタンドを追加し、未来の燃料を前借りしてしまう。
到達可能な例のみをテストし、空のヒープや数値の境界条件を見落とす。

フォローアップの質問

なぜすべてのスタンドで最大値を取らないのですか？

目的は給油回数の最小化だからです。早い段階で給油すると、到達可能性を改善することなく給油回数が増えてしまう可能性があります。燃料が不足するまで遅延させることで、すべての給油が実際の制約に対処するものになります。

部分的な給油が許可されている場合はどう変化しますか？

状態とコスト関数が変化します。価格やタンク容量が重要になる可能性があり、スタンドの燃料をすべて取得するという証明はそのまま適用できなくなります。

重複する位置でも正しく機能するのはなぜですか？

それらの距離は0であるため、任意の順序でpushできます。後続の区間で実際に燃料が必要になった際にも、ヒープは利用可能な最大量を適切に提供します。

実際に給油したスタンドを返すにはどうすればよいですか？

各ヒープ値とともにスタンドのインデックスを保存し、popされるたびにそのインデックスを記録します。記録されたインデックスを位置または選択順でソートして、ルートを再構築します。