合并 Python 中的区间

假设我们有一组区间，我们必须合并所有重叠的区间。因此，如果区间为 [[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]]

更新于:2020年5月4日

1千次观看

开启你的 职业生涯

完成课程获得认证

开始
广告