ধরুন আমাদের কাছে ব্যবধানের একটি সংগ্রহ আছে, আমাদের সমস্ত ওভারল্যাপিং ব্যবধান একত্র করতে হবে। সুতরাং যদি ব্যবধানগুলো হয় [[1,3], [2,6], [8,10], [15,18]], তাহলে মার্জ করার পরের ব্যবধানগুলো হবে [[1,6],[8,10] ],[15,18]]। এর কারণ হল দুটি ব্যবধান ছিল যেগুলি ওভারল্যাপ করছে, ব্যবধানগুলি হল [1,3] এবং [2,6], এগুলি [1,6]
আসুন ধাপগুলো দেখি -
- যদি ব্যবধান তালিকার দৈর্ঘ্য 0 হয়, তাহলে একটি ফাঁকা তালিকা ফেরত দিন
- দ্রুত সাজানোর পদ্ধতি ব্যবহার করে ব্যবধান তালিকা সাজান
- স্ট্যাক :=একটি খালি স্ট্যাক, এবং স্ট্যাকের মধ্যে বিরতি[0] ঢোকান
- আমি সীমা 1 থেকে ব্যবধানের দৈর্ঘ্য - 1
- last_element :=স্ট্যাকের শীর্ষ উপাদান
- যদি last_element এর শেষ>=ব্যবধানের প্রথম উপাদান[i], তারপর
- শেষ_এলিমেন্টের শেষ =ব্যবধানের শেষের সর্বোচ্চ[i], এবং শেষ_এলিমেন্টের শেষ
- স্ট্যাক থেকে পপ উপাদান
- স্ট্যাকের মধ্যে শেষ_এলিমেন্ট পুশ করুন
- অন্যথায় পুশ ইন্টারভাল[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]]