สมมติว่าเรามีชุดของช่วงเวลา เราต้องรวมช่วงเวลาที่ทับซ้อนกันทั้งหมด ดังนั้นหากช่วงเวลาเช่น [[1,3], [2,6], [8,10], [15,18]] ช่วงเวลาหลังจากการรวมจะเป็น [[1,6],[8,10 ],[15,18]]. นี่เป็นเพราะว่ามีสองช่วงที่ซ้อนทับกัน ช่วงคือ [1,3] และ [2,6] ซึ่งรวมเข้ากับ [1,6]
ให้เราดูขั้นตอน -
- ถ้ารายการช่วงเวลาเป็น 0 ให้ส่งคืนรายการว่าง
- เรียงลำดับรายการช่วงเวลาโดยใช้กลไกการเรียงลำดับอย่างรวดเร็ว
- stack :=สแต็กว่าง และแทรกช่วงเวลา[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]]
