Giả sử chúng ta có một tập hợp các khoảng, chúng ta phải hợp nhất tất cả các khoảng trùng nhau. Vì vậy, nếu các khoảng như [[1,3], [2,6], [8,10], [15,18]], thì các khoảng sau khi hợp nhất sẽ là [[1,6], [8,10 ], [15,18]]. Điều này là do có hai khoảng chồng lên nhau, các khoảng là [1,3] và [2,6], chúng được hợp nhất thành [1,6]
Hãy để chúng tôi xem các bước -
- nếu độ dài danh sách khoảng thời gian là 0, thì trả về một danh sách trống
- sắp xếp danh sách khoảng thời gian bằng cách sử dụng cơ chế nhanh chóng
- ngăn xếp:=ngăn xếp trống và chèn các khoảng [0] vào ngăn xếp
- cho tôi trong phạm vi từ 1 đến độ dài của khoảng - 1
- last_element:=phần tử trên cùng của ngăn xếp
- if end of last_element> =phần tử đầu tiên của khoảng [i], thì
- end of last_element =tối đa của cuối khoảng [i] và cuối của last_element
- phần tử pop từ ngăn xếp
- đẩy last_element vào ngăn xếp
- khác đẩy các khoảng [i] vào ngăn xếp
- trả về ngăn xếp
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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]]))
Đầu vào
[[1,3],[2,6],[8,10],[15,18]]
Đầu ra
[[1, 6], [8, 10], [15, 18]]