Pythonで解く「ヒーター」問題 ― 全ての家を暖める最小半径を求めるアルゴリズム

ヒーター問題とは

一定の暖房半径を持つ標準的なヒーターを設計し、すべての家を暖めることを考えます。水平線上に並ぶ家とヒーターの位置情報が与えられたとき、すべての家を確実にカバーできるヒーターの最小半径を求めるのがこの問題の目的です。

具体的には、家の位置リストとヒーターの位置リストがそれぞれ別に渡され、出力としては必要な最小の半径を返します。

例えば、入力が [1,2,3,4] と [1,4] の場合、出力は 1 となります。ヒーターが位置 1 と 4 に配置されており、半径 1 に設定すれば、位置 2 と 3 の家も含めてすべての家を暖めることができるためです。

解法のアプローチ

この問題を効率的に解くには、二分探索(bisect)を活用します。各家について、最も近いヒーターまでの距離を求め、その中で最大の値が答えになります。手順は以下の通りです。

• 家のリスト(houses)をソートする
• ヒーターのリスト(heaters)をソートする
• res := 家の配列と同じサイズの配列を作成し、無限大(inf)で初期化する
• i を 0 から家の数-1 までループする
  • h := houses[i](現在の家の位置)
  • ind := ソート順を保ったまま h を heaters に挿入できる左端のインデックス(二分探索で取得)
  • ind が heaters のサイズと等しい場合(家が一番右のヒーターより右側にあるとき)
    • res[i] := min(res[i], |h − heaters[-1]|)
  • そうでなく ind が 0 の場合(家が一番左のヒーターより左側にあるとき)
    • res[i] := min(res[i], |h − heaters[0]|)
  • それ以外の場合(家が2つのヒーターの間にあるとき)
    • res[i] := min(res[i], |h − heaters[ind]|, |h − heaters[ind−1]|) — 左右どちらか近い方のヒーターとの距離を採用
• res の最大値を返す(これが求めるべき最小半径)

実装例

理解を深めるために、以下の Python コードを見てみましょう。bisect_left 関数を使うことで、挿入位置を O(log n) で高速に求められます。

from bisect import bisect_left
class Solution:
    def findRadius(self, houses, heaters):
        houses.sort()
        heaters.sort()
        res = [float('inf')]*len(houses)
        for i in range(len(houses)):
            h = houses[i]
            ind = bisect_left(heaters, h)
            if ind==len(heaters):
                res[i] = min(res[i], abs(h - heaters[-1]))
            elif ind == 0:
                res[i] = min(res[i], abs(h - heaters[0]))
            else:
                res[i] = min(res[i], abs(h - heaters[ind]), abs(h - heaters[ind-1]))
        return max(res)

ob = Solution()
print(ob.findRadius([1,2,3,4],[1,4]))

入力

[1,2,3,4],[1,4]

出力

1

計算量について

ソートに O(n log n + m log m)、各家に対する二分探索に O(log m)(n は家の数、m はヒーターの数)かかるため、全体の計算量は O((n + m) log(n + m)) 程度となり、非常に効率的な解法です。