Hợp nhất các khoảng trong Python

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]]