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

मान लीजिए हमारे पास गैर-ओवरलैपिंग अंतरालों की एक सूची है। ये समाप्ति समय के आधार पर सॉर्ट किए गए हैं। हमारे पास एक और अंतराल target है। target को मर्ज करने के बाद अंतिम अंतराल ज्ञात करें ताकि अंतराल अभी भी गैर-ओवरलैपिंग और सॉर्टेड रहें।

उदाहरण के लिए, intervals = [[1,15],[25,35],[75,90]], target = [10,30] के लिए आउटपुट [[1,35],[75,90]] होगा।

एल्गोरिदम

• target को iv में जोड़ें
• iv को प्रारंभ समय के आधार पर सॉर्ट करें
• res := [iv[0]]
• i=1 से len(iv)-1 तक:
  • यदि iv[i][0] <= res[-1][1], तो res[-1][1] = max(res[-1][1], iv[i][1])
  • अन्यथा res.append(iv[i])
• res वापस करें

उदाहरण

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]]