पायथन में एक अंतराल सूची में सम्मिलित करने के लिए एक न्यूनतम संभव अंतराल खोजने का कार्यक्रम

मान लीजिए कि हमारे पास अंतराल नामक संख्याओं की एक 2D सूची है, जहां प्रत्येक पंक्ति [प्रारंभ, अंत] (समावेशी) अंतराल का प्रतिनिधित्व करती है। एक अंतराल [ए, बी] (ए <बी) के लिए, इसका आकार (बी - ए) है। हमें दी गई सूची में एक अंतराल इस तरह जोड़ना चाहिए कि सभी अंतरालों को मिलाने के बाद, हमें ठीक एक सीमा शेष मिले। हमें जोड़े गए अंतराल का न्यूनतम संभव आकार खोजना होगा।

इसलिए, यदि इनपुट अंतराल =[[15, 20], [30, 50]] की तरह है, तो आउटपुट 10 होगा, क्योंकि हम अंतराल [20, 30] जोड़ सकते हैं जो कि सबसे छोटा संभव अंतराल है।

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

• ईवेंट :=एक नई सूची
• प्रत्येक प्रारंभ और समाप्ति समय s के लिए, e अंतराल में, करें
  • इवेंट के अंत में (ओं, 1) डालें
  • इवेंट के अंत में (e, -1) डालें
• सूची ईवेंट क्रमबद्ध करें
• curr_status :=0, last:=null
• अंतराल:=एक जोड़ी [0, 0]
• घटनाओं में प्रत्येक जोड़ी (समय, स्थिति) के लिए, करें
  • यदि curr_status 0 और अंतिम और समय> अंतिम के समान है, तो
    • यदि अंतराल [0] 0 के समान है, तो
      • अंतराल[0] :=अंतिम
    • अंतराल[1] :=समय
  • अंतिम:=समय
  • curr_status :=curr_status + status
• वापसी अंतराल[1] - अंतराल[0]

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

उदाहरण

class Solution:
   def solve(self, intervals):
      events = []
      for s, e in intervals:
         events.append((s, 1))
         events.append((e, -1))
      events.sort()
      curr_status = 0
      last = None
      interval = [0, 0]
      for time, status in events:
         if curr_status == 0 and last and time > last:
            if interval[0] == 0:
               interval[0] = last
            interval[1] = time
         last = time
         curr_status += status
      return interval[1] - interval[0]
ob = Solution()
intervals = [[15, 20],[30, 50]] print(ob.solve(intervals))

इनपुट

[[15, 20],[30, 50]]

आउटपुट

10