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

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

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन मान्य() परिभाषित करें। इसमें r लगेगा

• last_location :=nums[0] + r

• गिनती :=1

• मैं के लिए 0 से लेकर अंकों के आकार तक, करें

  • वैल:=अंक [i]

  • अगर वैल - last_location> r, तो

    • गिनती :=गिनती + 1

    • last_location :=वैल + आर

• गिनती <=3 होने पर सही लौटें, अन्यथा गलत

• मुख्य विधि से निम्न कार्य करें -

• सूची संख्या क्रमित करें

• बायां :=0

• दाएं:=अंकों का अंतिम तत्व

• रेस :=inf

• आईटीआर:=0

• जबकि बाएँ <=दाएँ और itr <20, करें

  • मध्य:=बाएँ + (दाएँ - बाएँ) / 2

  • यदि मान्य (मध्य) सत्य है, तो

    • रेस :=न्यूनतम रेस और मध्य

    • दाएं:=मध्य

  • अन्यथा,

    • बाएं :=मध्य

    • आईटीआर:=आईटीआर + 1

• रिटर्न रेस

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

class Solution:
   def solve(self, nums):
      def valid(r):
         last_location = nums[0] + r
         count = 1
         for i in range(len(nums)):
            val = nums[i]
            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