合并重叠间隔python

Question

目前,我有以下间隔:

temp_tuple = [[-25, -14], [-21, -16], [-20, -15], [-10, -7], [-8, -5], [-6, -3], [2, 4], [2, 3], [3, 6], [12, 15], [13, 18], [14, 17], [22, 27], [25, 30], [26, 29]]

按下限按升序排列.我的任务是合并重叠的间隔,以便结果出现:

[-25, -14]
[-10, -3]
[2, 6]
[12, 18]
[22, 30]

我的第一次尝试涉及删除完全在先前间隔内的间隔,例如[-21,-16],其落在[-25,-14]内.但是删除列表中的对象会干扰循环条件.我第二次尝试删除不必要的间隔是:

i = 0
j = 1
while i < len(temp_tuples):
    while j < len(temp_tuples):
        if temp_tuples[i][1] > temp_tuples[j][1]:
            del temp_tuples[j]
        j += 1
    i += 1

但由于某种原因,这并没有删除所有不必要的间隔.我该怎么办？

Answer 1

如果您改为设置新列表,它会使处理更容易(如在思考中).您还可以保留原始数据.

temp_tuple.sort(key=lambda interval: interval[0])
merged = [temp_tuple[0]]
for current in temp_tuple:
    previous = merged[-1]
    if current[0] <= previous[1]:
        previous[1] = max(previous[1], current[1])
    else:
        merged.append(current)

如果你现在print(merged)它会输出:

[[-25, -14], [-10, -3], [2, 6], [12, 18], [22, 30]]

Answer 2

这是我想出的一个 numpy 解决方案：

import numpy as np

def merge_intervals(intervals):
    starts = intervals[:,0]
    ends = np.maximum.accumulate(intervals[:,1])
    valid = np.zeros(len(intervals) + 1, dtype=np.bool)
    valid[0] = True
    valid[-1] = True
    valid[1:-1] = starts[1:] >= ends[:-1]
    return np.vstack((starts[:][valid[:-1]], ends[:][valid[1:]])).T

#example
a=[]
a.append([1,3])
a.append([4,10])
a.append([5,12])
a.append([6,8])
a.append([20,33])
a.append([30,35])

b = np.array(a)

print("intervals")
print(b)
print()
print("merged intervals")
print(merge_intervals(b))

输出：

intervals
[[ 1  3]
 [ 4 10]
 [ 5 12]
 [ 6  8]
 [20 33]
 [30 35]]

merged intervals
[[ 1  3]
 [ 4 12]
 [20 35]]

请注意，输入数组必须按起始位置排序。