পাইথনে হিটারস (Heaters) — ন্যূনতম রেডিয়াস নির্ণয়

সমস্যা বিবরণ

হাউস এবং হিটারদের পজিশন একটি হরিজন্টাল লাইনে দেওয়া থাকে। সব হাউস কভার করতে হিটারদের ন্যূনতম উষ্ণতা ত্রিজ্যা (radius) বের করুন।

উদাহরণ

houses = [1,2,3,4], heaters = [1,4] → আউটপুট: 1

হিটার ১ এবং ৪-এ। রেডিয়াস ১ দিলে সব হাউস (১,২,৩,৪) কভার হয়।

এলগরিদম (Binary Search)

1. houses.sort(), heaters.sort()।
2. প্রতিটি হাউস h এর জন্য bisect_left(heaters, h) দিয়ে নিকটতম হিটার খুঁজুন।
3. নিকটতম হিটার(গুলো) থেকে দূরত্বের মিনিমাম নিন।
4. সব হাউসের এই মিনিমাম দূরত্বের মধ্যে সর্বোচ্চটি = জবাব।

পাইথন বাস্তবায়ন

from bisect import bisect_left

class Solution:
    def findRadius(self, houses, heaters):
        houses.sort()
        heaters.sort()
        res = [float('inf')] * len(houses)
        for i, h in enumerate(houses):
            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

ইনপুট / আউটপুট

ইনপুট: [1,2,3,4], [1,4]
আউটপুট: 1