पायथन में अधिकतम भवन ऊंचाई खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक मान n है और जोड़े की एक और सूची है जिसे प्रतिबंध कहा जाता है। हम एक शहर में नई इमारतें बनाना चाहते हैं। लेकिन कुछ प्रतिबंध हैं। हम एक लाइन में बना सकते हैं और इमारतों को 1 से n तक लेबल किया जाता है। प्रतिबंधों के दो पैरामीटर हैं, इसलिए प्रतिबंध [i] =(id_i, max_height_i) इंगित करता है कि id_i की ऊंचाई max_height_i से कम या उसके बराबर होनी चाहिए। नई इमारतों की ऊंचाई पर शहर के प्रतिबंध इस प्रकार हैं -

प्रत्येक भवन की ऊंचाई 0 या सकारात्मक मान होनी चाहिए।
पहली इमारत की ऊंचाई 0 होनी चाहिए।
किन्हीं दो आसन्न इमारतों के बीच की ऊंचाई का अंतर 1 से अधिक नहीं हो सकता है।

हमें सबसे ऊँची इमारत की अधिकतम संभव ऊँचाई ज्ञात करनी है।

इसलिए, यदि इनपुट n =5, प्रतिबंध =[[2,1], [4,3]] की तरह है, तो आउटपुट 4 होगा क्योंकि हमें अधिकतम संभव ऊंचाई का पता लगाना है, इसलिए यह 4 हो सकता है जैसा कि दिखाया गया है आरेख।

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

अगर प्रतिबंध खाली हैं, तो
- वापसी n-1
resi :=आईडी के आधार पर सूची प्रतिबंधों को क्रमबद्ध करें
कश्मीर:=0
आईडीएक्स :=1
रेसी में प्रत्येक री के लिए, करें
- पुनः[1] :=न्यूनतम पुनः[1] और (k+re[0]-idx)
- कश्मीर:=पुनः[1]
- idx :=re[0]
k :=रेसी में अंतिम तत्व की अधिकतम ऊंचाई
idx :=resi में अंतिम तत्व की आईडी
सूची को उलट दें
पहले आइटम के बाद से प्रत्येक री इन रेसी के लिए, करें
- पुनः[1] :=न्यूनतम पुनः[1] और (k-re[0]+idx)
- कश्मीर:=पुनः[1]
- idx :=re[0]
सूची को उलट दें
च :=0
आईडीएक्स :=1
रेस :=0
रेसी में प्रत्येक री के लिए, करें
- ff :=न्यूनतम (f+re[0]-idx) और re[1]
- res :=अधिकतम रेस और भागफल (re[0] - idx + f + ff)/2
- idx :=re[0]
- च :=एफएफ
अधिकतम (f+n-idx) और रेस करें

उदाहरण

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

def solve(n, restrictions):
   if not restrictions:
      return n-1
   resi = sorted(restrictions, key = lambda x:x[0])

   k = 0
   idx = 1
   for re in resi:
      re[1] = min(re[1], k+re[0]-idx)
      k = re[1]
      idx = re[0]
   k = resi[-1][1]
   idx = resi[-1][0]
   resi.reverse()
   for re in resi[1:]:
      re[1] = min(re[1], k-re[0]+idx)
      k = re[1]
      idx = re[0]
   resi.reverse()

   f = 0
   idx = 1
   res = 0
   for re in resi:
      ff = min(f+re[0]-idx, re[1])
      res = max(res, (re[0] - idx + f + ff) // 2)
      idx = re[0]
      f = ff
   return max(f+n-idx,res)

n = 5
restrictions = [[2,1],[4,3]]
print(solve(n, restrictions))

इनपुट

5, [[2,1],[4,3]]