पायथन में सड़क पर सभी घरों को रोशन करने के लिए न्यूनतम त्रिज्या ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है जो 1-आयामी रेखा पर घरों की स्थिति दर्शाती है। अब मान लीजिए हमारे पास 3 स्ट्रीट लाइट हैं जिन्हें हम रेखा पर कहीं भी रख सकते हैं और स्थिति x पर एक लाइट [x-r, x+r] रेंज में सभी घरों को रोशन करती है। हमें सबसे छोटा r ज्ञात करना है जिससे सभी घर रोशन हो जाएं।

उदाहरण के लिए, nums = [4,5,6,7] के लिए आउटपुट 0.5 होगा, क्योंकि हम लैंप को 4.5, 5.5 और 6.5 पर रख सकते हैं ताकि r=0.5 हो। ये तीन लाइटें सभी 4 घरों को रोशन कर सकती हैं।

एल्गोरिदम (बाइनरी सर्च + ग्रीडी)

• valid(r) फ़ंक्शन परिभाषित करें:
  • last_location := nums[0] + r, count := 1
  • प्रत्येक val in nums के लिए:
    • यदि val - last_location > r, तो count++, last_location = val + r
  • count <= 3 वापस करें
• मुख्य विधि से:
  • nums को सॉर्ट करें
  • left := 0, right := nums[-1], res := inf, itr := 0
  • जब left <= right और itr < 20:
    • mid = left + (right-left)/2
    • यदि valid(mid), तो res = min(res, mid), right = mid
    • अन्यथा left = mid
    • itr++
  • res वापस करें

उदाहरण

class Solution:
    def solve(self, nums):
        def valid(r):
            last_location = nums[0] + r
            count = 1
            for val in nums:
                if val - last_location > r:
                    count += 1
                    last_location = val + r
            return count <= 3
        nums.sort()
        left = 0
        right = nums[-1]
        res = float("inf")
        itr = 0
        while left <= right and itr < 20:
            mid = left + (right - left) / 2
            if valid(mid):
                res = min(res, mid)
                right = mid
            else:
                left = mid
            itr += 1
        return res

ob = Solution()
nums = [4,5,6,7]
print(ob.solve(nums))

इनपुट

[4,5,6,7]

आउटपुट

0.5