Heaters ใน Python: หารัศมีขั้นต่ำของ हीटरให้ครอบคลุมบ้านทั้งหมด

มีตำแหน่งบ้านและฮีตเตอร์บนเส้นตรง ฮีตเตอร์แต่ละตัวให้ความอบอุ่นในรัศมี r หารัศมี r น้อยที่สุดที่ทำให้ทุกบ้านอยู่ในรัศมีของฮีตเตอร์อย่างน้อย 1 ตัว

ตัวอย่าง

houses = [1,2,3,4], heaters = [1,4] → รัศมี 1 (ฮีตเตอร์ที่ 1 ครอบคลุม 1-2, ฮีตเตอร์ที่ 4 ครอบคลุม 3-4)

ขั้นตอนการแก้ปัญหา (Binary Search)

1. เรียงลำดับ houses และ heaters
2. แต่ละบ้าน: หาเฮตเตอร์ใกล้ที่สุดด้วย bisect_left
3. คำนวณระยะห่างน้อยที่สุดไปยังฮีตเตอร์ใกล้เคียง
4. คำตอบ = ค่าสูงสุดของระยะห่างน้อยที่สุดเหล่านั้น

การติดตั้งใน Python

from bisect import bisect_left

class Solution:
    def findRadius(self, houses, heaters):
        houses.sort()
        heaters.sort()
        max_dist = 0
        for h in houses:
            i = bisect_left(heaters, h)
            if i == len(heaters):
                dist = abs(h - heaters[-1])
            elif i == 0:
                dist = abs(h - heaters[0])
            else:
                dist = min(abs(h - heaters[i]), abs(h - heaters[i-1]))
            max_dist = max(max_dist, dist)
        return max_dist

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

อินพุต / เอาต์พุต

Input: [1,2,3,4], [1,4]
Output: 1