โปรแกรมหารัศมีขั้นต่ำเพื่อส่องสว่างบ้านทั้งหมดใน Python

ได้รับตำแหน่งบ้านบนเส้นตรง 1D (nums) มีโคมไฟ 3 ดวง วางได้ทุกที่ โคมที่ x ส่องสว่างช่วง [x-r, x+r] หา r น้อยที่สุด ให้ส่องสว่างบ้านทั้งหมด

ตัวอย่าง

Input: [4, 5, 6, 7]

Output: 0.5

วางโคมที่ 4.5, 5.5, 6.5 → ครอบคลุมทั้ง 4 บ้าน

แนวทางแก้ปัญหา

Binary Search คำตอบ + Greedy Check:

1. เรียงลำดับตำแหน่งบ้าน
2. Binary search r ในช่วง [0, max_pos]
3. ฟังก์ชัน valid(r): วางโคมแรกที่ nums[0] + r แล้ววางต่อไปเรื่อยๆ นับจำนวนโคม → ต้อง ≤ 3

การใช้งาน (Python)

class Solution:
    def solve(self, nums):
        nums.sort()
        
        def valid(r):
            last = nums[0] + r  # ตำแหน่งโคมล่าสุด
            count = 1
            for pos in nums:
                if pos - last > r:
                    count += 1
                    last = pos + r
            return count <= 3
        
        left, right = 0.0, float(nums[-1])
        res = float('inf')
        
        for _ in range(50):  # 50 iterations พอสำหรับ precision
            mid = (left + right) / 2
            if valid(mid):
                res = mid
                right = mid
            else:
                left = mid
        
        return res

# ทดสอบ
ob = Solution()
print(ob.solve([4, 5, 6, 7]))  # Output: 0.5

ความซับซ้อน

• Time Complexity: O(N log MaxPos)
• Space Complexity: O(1)

ใช้ iteration คงที่ (50 รอบ) แทน while loop เพื่อ precision ที่แน่นอน