पायथन में हीटर्स

मान लीजिए हमें एक मानक हीटर डिज़ाइन करना है जिसकी एक निश्चित गर्म त्रिज्या हो जो सभी घरों को गर्म कर सके। अब, हमें एक क्षैतिज रेखा पर घरों और हीटर्स की स्थितियां दी गई हैं, हमें हीटर्स की न्यूनतम त्रिज्या ढूंढनी है ताकि सभी घर उन हीटर्स द्वारा कवर किए जा सकें। इसलिए, हम घरों और हीटर्स को अलग-अलग प्रदान करेंगे, और हमारा अपेक्षित आउटपुट हीटर्स की न्यूनतम त्रिज्या मानक होगा।

उदाहरण के लिए, यदि इनपुट [1,2,3,4],[1,4] है, तो आउटपुट 1 होगा क्योंकि दो हीटर्स स्थिति 1 और 4 पर रखे गए थे। हमें त्रिज्या 1 का उपयोग करना होगा, तब सभी घर गर्म हो सकते हैं।

हल करने के चरण

घरों की सूची को सॉर्ट करें
हीटर्स की सूची को सॉर्ट करें
res := घरों की सरणी के आकार का एक सरणी, अनंत से भरा हुआ
i को 0 से घरों के आकार तक लूप करें:
- h := houses[i]
- ind := h को हीटर्स में डालने के लिए बायां सबसे सूचकांक ताकि सूची सॉर्टेड रहे
- यदि ind, हीटर्स के आकार के बराबर है, तो:
  - res[i] := min(res[i], |h - heaters[-1]|)
- अन्यथा जब ind 0 के बराबर है, तो:
  - res[i] := min(res[i], |h - heaters[0]|)
- अन्यथा:
  - res[i] := min(res[i], |h - heaters[ind]|, |h - heaters[ind-1]|)
res का अधिकतम वापस करें

उदाहरण

from bisect import bisect_left
class Solution:
    def findRadius(self, houses, heaters):
        houses.sort()
        heaters.sort()
        res = [float('inf')] * len(houses)
        for i in range(len(houses)):
            h = houses[i]
            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,2,3,4],[1,4]