पायथन में अंतराल की सूची से सबसे लंबे अंतराल की लंबाई खोजने का कार्यक्रम

मान लीजिए कि हमारे पास अंतराल की एक सूची है जहां प्रत्येक अंतराल [प्रारंभ, अंत] के रूप में है। हमें किसी भी अतिव्यापी अंतराल को मर्ज करके सबसे लंबा अंतराल खोजना होगा।

इसलिए, यदि इनपुट [[1, 6], [4, 9], [5, 6], [11, 14], [16, 20]] जैसा है, तो आउटपुट 9 होगा, जैसे विलय के बाद, हमारे पास 9 की लंबाई का अंतराल [1, 9] है।

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

• सूची अंतरालों को क्रमबद्ध करें
• संघ:=अंतराल सूची से पहला अंतराल
• सर्वश्रेष्ठ:=संघ[अंत] - संघ[शुरू] + 1
• प्रत्येक प्रारंभ समय s और समाप्ति समय e अंतराल में पहले वाले को छोड़कर, करें
  • अगर एस <=संघ[अंत], तो
    • संघ[अंत] :=अधिकतम संघ[अंत] और ई
  • अन्यथा,
    • संघ :=एक नया अंतराल [s, e]
  • सर्वश्रेष्ठ:=अधिकतम सर्वोत्तम और संघ[अंत] - संघ[प्रारंभ] + 1
• सर्वोत्तम वापसी

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

उदाहरण

class Solution:
   def solve(self, intervals):
      intervals.sort()
      union = intervals[0]
      best = union[1] - union[0] + 1
      for s, e in intervals[1:]:
         if s <= union[1]:
            union[1] = max(union[1], e)
         else:
            union = [s, e]
            best = max(best, union[1] - union[0] + 1)
      return best
ob = Solution()
intervals = [[1, 6],[4, 9],[5, 6],[11, 14],[16, 20]]
print(ob.solve(intervals))

इनपुट

[[1, 6],[4, 9],[5, 6],[11, 14],[16, 20]]

आउटपुट

9