Pythonのヒーター

すべての家を暖めるために、固定された暖かい半径を持つ標準的なヒーターを設計する必要があるとします。これで、家とヒーターの位置を水平線上に指定しました。すべての家がこれらのヒーターで覆われるように、ヒーターの最小半径を見つける必要があります。そのため、住宅とヒーターを別々に提供し、予想される出力はヒーターの最小半径標準になります。

したがって、入力が[1,2,3,4]、[1,4]の場合、2つのヒーターが位置1と4に配置されているため、出力は1になります。半径1を使用する必要があります。その後、すべて家を暖めることができます。

これを解決するには、次の手順に従います-

• リストハウスを並べ替える

• リストヒーターを並べ替える

• res：=家の配列と同じサイズの配列で、infを使用してこれを埋めます

• 0から家のサイズまでの範囲のiの場合、実行します

  • h：=家[i]

  • ind：=リストがソートされたままになるように、ヒーターにhを挿入するために最も左のインデックス

  • indがヒーターのサイズと同じである場合、

    • res [i]：=最小のres [i]、|h-ヒーター[-1]|

  • それ以外の場合、indが0と同じ場合、

    • res [i]：=最小のres [i]、|h-ヒーター[0]|

  • それ以外の場合

    • res [i]：=最小のres [i]、|h-ヒーター[ind]| 、|h-ヒーター[ind-1]|

• 最大解像度を返す

例

理解を深めるために、次の実装を見てみましょう-

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