मान लीजिए हमारे पास अंतरालों का एक संग्रह है, हमें सभी ओवरलैपिंग अंतरालों को मर्ज करना है। इसलिए यदि अंतराल [[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]]