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

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

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

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• intervals को सॉर्ट करें
• union := intervals[0]
• best := union[1] - union[0] + 1
• प्रत्येक (s, e) के लिए intervals[1:] में:
  • यदि s <= union[1]:
    • union[1] := max(union[1], e)
  • अन्यथा:
    • union := [s, e]
  • best := max(best, union[1] - union[0] + 1)
• best लौटाएं

उदाहरण कोड

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