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

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

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

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

• events := एक नई सूची
• प्रत्येक प्रारंभ और अंत समय s, e के लिए intervals में, करें
  • (s, 1) को events के अंत में जोड़ें
  • (e, -1) को events के अंत में जोड़ें
• सूची events को सॉर्ट करें
• curr_status := 0, last := null
• interval := एक जोड़ी [0, 0]
• प्रत्येक जोड़ी (time, status) के लिए events में, करें
  • यदि curr_status, 0 के समान है और last और time > last, तो
    • यदि interval[0], 0 के समान है, तो
      • interval[0] := last
    • interval[1] := time
  • last := time
  • curr_status := curr_status + status
• interval[1] - interval[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