在Python中合并间隔
假设我们有一个间隔集合，我们必须合并所有重叠的间隔。因此，如果间隔类似于[[1,3]，[2,6]，[8,10]，[15,18]]，则合并后的间隔将为[[1,6]，[8,10]]，[15,18]]。这是因为有两个重叠的区间，区间为[1,3]和[2,6]，它们合并为[1,6]
让我们看看步骤-
如果间隔列表的长度为0，则返回一个空白列表
使用quicksort机制对间隔列表进行排序
stack：=一个空栈，并在栈中插入interval[0]
对于范围在1到间隔长度的i–1
last_element的结尾=interval[i]的最大结尾和last_element的结尾
堆栈中的弹出元素
将last_element推入堆栈
last_element：=栈顶元素
如果last_element的结尾>=interval[i]的第一个元素，则
否则将interval[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]]