पायथन में लक्ष्य अंतराल को मर्ज करके अंतराल खोजने का कार्यक्रम

मान लीजिए कि हमारे पास गैर-अतिव्यापी अंतरालों की एक सूची है। इन्हें समाप्ति समय के आधार पर क्रमबद्ध किया जाता है। हमारे पास एक और अंतराल लक्ष्य है, लक्ष्य विलय करने के बाद अंतिम अंतराल खोजें ताकि अंतराल अभी भी गैर-अतिव्यापी और क्रमबद्ध हों।

इसलिए, यदि इनपुट अंतराल =[[1, 15], [25, 35], [75, 90]], लक्ष्य =[10, 30] की तरह है, तो आउटपुट [[1, 35], [ 75, 90]] पहले दो अंतरालों के रूप में [1, 15] और [25, 35] को मिला दिया गया है।

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

• iv के अंत में लक्ष्य डालें

• प्रारंभ समय के आधार पर iv क्रमबद्ध करें

• रेस :=पहले अंतराल के साथ एक नई सूची

• मैं :=1

• जबकि मैं

  • यदि iv का प्रारंभ समय [i] <=रेस के अंतिम अंतराल का अंत समय है, तो

    • रेस के अंतिम अंतराल का अंत समय =अधिकतम (रेस के अंतिम अंतराल का अंतिम समय और iv[i] का अंतिम समय)

  • अन्यथा,

    • रेस के अंत में iv[i] डालें

  • मैं :=मैं + 1

• रिटर्न रेस

उदाहरण (पायथन)

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

class Solution:
   def solve(self, iv, target):
      iv.append(target)
      iv.sort(key=lambda x: x[0])
      res = [iv[0]]
      i = 1
      while i < len(iv):
         if iv[i][0] <= res[-1][1]:
            res[-1][1] = max(res[-1][1], iv[i][1])
         else:
            res.append(iv[i])
         i += 1
      return res
ob = Solution()
intervals = [
   [1, 15],
   [25, 35],
   [75, 90]
]
target = [10, 30]
print(ob.solve(intervals, target))

इनपुट

[[1, 15],[25, 35],[75, 90]], [10, 30]

आउटपुट

[[1, 35], [75, 90]]