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

मान लीजिए कि हमारे पास अंतरालों का एक संग्रह है, हमें सभी अतिव्यापी अंतरालों को मिलाना होगा। तो अगर अंतराल [[1,3], [2,6], [8,10], [15,18]] जैसे हैं, तो विलय के बाद अंतराल [[1,6], [8,10 होगा। ], [15,18]]। ऐसा इसलिए है क्योंकि दो अंतराल थे जो अतिव्यापी हैं, अंतराल [1,3] और [2,6] हैं, इन्हें [1,6]

आइए चरणों को देखें -

• यदि अंतराल सूची की लंबाई 0 है, तो एक रिक्त सूची लौटाएं
• क्विकसॉर्ट तंत्र का उपयोग करके अंतराल सूची को क्रमबद्ध करें
• स्टैक:=एक खाली स्टैक, और स्टैक में अंतराल[0] डालें
• i के लिए 1 से लेकर अंतराल की लंबाई तक - 1
  • last_element :=स्टैक का शीर्ष तत्व
  • यदि last_element का अंत>=अंतराल का पहला तत्व [i], तो
    • last_element का अंत =अंतराल के अंत का अधिकतम [i], और last_element का अंत
    • स्टैक से पॉप तत्व
    • last_element को स्टैक में पुश करें
  • अन्यथा अंतराल को पुश करें[i] स्टैक में
• रिटर्न स्टैक

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

उदाहरण

class Solution(object):
   def merge(self, intervals):
      """
      :type intervals: List[Interval]
      :rtype: List[Interval]
      """
      if len(intervals) == 0:
         return []
      self.quicksort(intervals,0,len(intervals)-1)
      #for i in intervals:
         #print(i.start, i.end)
      stack = []
      stack.append(intervals[0])
      for i in range(1,len(intervals)):
         last_element= stack[len(stack)-1]
         if last_element[1] >= intervals[i][0]:
            last_element[1] = max(intervals[i][1],last_element[1])
            stack.pop(len(stack)-1)
            stack.append(last_element)
         else:
            stack.append(intervals[i])
      return stack
   def partition(self,array,start,end):
      pivot_index = start
      for i in range(start,end):
         if array[i][0]<=array[end][0]:
            array[i],array[pivot_index] =array[pivot_index],array[i]
            pivot_index+=1
      array[end],array[pivot_index] =array[pivot_index],array[end]
      return pivot_index
   def quicksort(self,array,start,end):
      if start<end:
         partition_index = self.partition(array,start,end)
         self.quicksort(array,start,partition_index-1)
         self.quicksort(array, partition_index + 1, end)
ob1 = Solution()
print(ob1.merge([[1,3],[2,6],[8,10],[15,18]]))

इनपुट

[[1,3],[2,6],[8,10],[15,18]]

आउटपुट

[[1, 6], [8, 10], [15, 18]]