Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

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


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

चरण देखें -

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

  1. Python में हिस्टोग्राम में सबसे बड़ा आयत Python में हिस्टोग्राम में सबसे बड़ा आयत

    मान लीजिए हमारे पास एक पूर्णांक सरणी है जो हिस्टोग्राम की ऊंचाई दर्शाती है। प्रत्येक बार की इकाई चौड़ाई है। हमें निम्नानुसार सबसे बड़े क्षेत्र का आयत ढूंढना है −इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −स्टैक बनाएं, i := 0, ans := 0 सेट करेंजब तक i < heights का आकार, तबयदि स्टैक में 0 तत्व हैं

  1. Python में वर्षा जल संग्रहण Python में वर्षा जल संग्रहण

    मान लीजिए हमारे पास n गैर-ऋणात्मक पूर्णांकों की एक सरणी है। ये एक ऊंचाई मानचित्र दर्शाते हैं जहां प्रत्येक बार की चौड़ाई 1 है, हमें गणना करनी है कि बारिश के बाद यह कितना पानी रोक सकता है। इसलिए मानचित्र इस तरह होगा −यहां हम 6 नीले बॉक्स देख सकते हैं, इसलिए आउटपुट 6 होगा।इसे हल करने के लिए, हम इन चरण

  1. पायथन प्रोग्राम: मर्ज सॉर्ट पायथन प्रोग्राम: मर्ज सॉर्ट

    इस लेख में हम दी गई समस्या के समाधान के बारे में जानेंगे। समस्या कथन हमें एक सरणी दी गई है, हमें मर्ज सॉर्ट की अवधारणा का उपयोग करके इसे क्रमबद्ध करना है। यहां हम अधिकतम तत्व को अंत में रखते हैं। यह तब तक दोहराया जाता है जब तक सरणी क्रमबद्ध नहीं हो जाती। उदाहरण # मर्ज फ़ंक्शन def merge(arr, l, m, r)