Слияние питонов с перекрывающимися интервалами
В настоящее время у меня есть интервалы:
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
но это не удаляет все ненужные интервалы по некоторым причинам. Что я должен делать?
5 ответов
Решение
Это немного облегчает обработку (как вы думаете), если вместо этого вы настраиваете новый список. Вы также можете сохранить свои исходные данные.
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]]
Это простое решение, которое я придумал:
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]]
Обратите внимание, что входной массив должен быть отсортирован по начальным позициям.
Я сделал некоторые улучшения на основе ответа Валлентина , в основном используяcopy.deepcopyчтобы предотвратить любые изменения во входных данных.
Обратите внимание, что использованиеsorted()или.copy()недостаточно, поскольку подэлементы изменяются при любом слиянии.
Я также добавил.sort()вызов каждого интервала для обработки несортированных входных данных, а также более явный вызов начальной сортировки для ясности.
Код:
import copy
def mergeIntervals(input_array, preserve_input=True):
'''
Python3 program for merging overlapping intervals.
If preserve_input is False, the input_array can be modified! Not just sorted, but even sub-elements can change!
See:
https://www.educative.io/answers/what-is-the-merge-overlapping-intervals-problem
https://www.geeksforgeeks.org/merging-intervals/
https://stackoverflow.com/questions/43600878/merging-overlapping-intervals
'''
if preserve_input:
intervals = copy.deepcopy(input_array)
else:
intervals = input_array
# Sort the given list of time intervals in ascending order of starting time.
intervals.sort(key=lambda interval: interval[0])
intervals[0].sort() # deal with unsorted input
# Create a stack with the first interval
merged = [intervals[0]]
for current in intervals[1:]:
current.sort() # deal with unsorted input
previous = merged[-1]
# Check for overlapping interval
if current[0] <= previous[-1]: # If it’s overlapping, then merge them into one interval;
previous[-1] = max(previous[-1], current[-1])
else: # otherwise, push it in the stack.
merged.append(current)
return merged
##### Testing code:
A_list = []
# Example from original question:
input_array = [[-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]]
A_list.append(input_array)
# Example with unsorted elements and sub-elements:
input_array = [[4, 2], [3, 1]]
A_list.append(input_array)
for preserve_input in [False, True]:
print(f'==> preserve_input = {preserve_input}')
for idx, a in enumerate(A_list):
print('------> idx = ', idx)
input_array = copy.deepcopy(a)
print('input before:', input_array)
output_array = mergeIntervals(input_array, preserve_input=preserve_input)
print('input after:', input_array)
print('output', output_array)
if input_array != a:
print('Input modified!')
if preserve_input:
raise
else:
print('No change in input.')
Выход:
Особо отметим изменение[22, 27]к[22, 30]в первом примере, ближе к концу.
==> preserve_input = False
------> idx = 0
input before: [[-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]]
input after: [[-25, -14], [-21, -16], [-20, -15], [-10, -3], [-8, -5], [-6, -3], [2, 6], [2, 3], [3, 6], [12, 18], [13, 18], [14, 17], [22, 30], [25, 30], [26, 29]]
output [[-25, -14], [-10, -3], [2, 6], [12, 18], [22, 30]]
Input modified!
------> idx = 1
input before: [[4, 2], [3, 1]]
input after: [[1, 4], [2, 4]]
output [[1, 4]]
Input modified!
==> preserve_input = True
------> idx = 0
input before: [[-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]]
input after: [[-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]]
output [[-25, -14], [-10, -3], [2, 6], [12, 18], [22, 30]]
No change in input.
------> idx = 1
input before: [[4, 2], [3, 1]]
input after: [[4, 2], [3, 1]]
output [[1, 4]]
No change in input.
#Given an array of intervals in sorted order and a new interval, return a sorted array after merging the interval
def mergeinter(intervals,newinter):
n = len(intervals)
start = newinter[0]# we mark the start and end of the new interval to be merged
end = newinter[1]
right,left = 0,0
while right < n:# we track where this new interval belongs, i.e. how many interval are to the left of it and how many are to the right
if start <= intervals[right][1]:# we find the first interval before which it fits
if end < intervals[right][0]:# this checks if the interval is disjoint and lies between two given intervals
break# in this case we have nothing to do and go to line 29 directly
start = min(start,intervals[right][0])# if it intersects with the given intervals then we just update and merge the ends
end = max(end,intervals[right][1])
else:# counting how many to the left continuing from line 20
left += 1
right += 1# moving right to find the fit continuation of line 20 and even if we merge in line 25, we go to the next interval before
return intervals[:left] + [(start,end)] + intervals[right:] # we return starting from the next interval
#Given a collection of intervals, merge all overlapping intervals and return sorted list of disjoint intervals.
def merge(I):
I.sort(key:lambda i:i[0])# sorting according to the start of all intervals
res = []# we start from the last of the given arr of lists and check the ends of the intervals and merge from the end
for i in I:
if not res or res[-1][0] < i[1]:# if res is empty then we put an elem in it from I
res.append(i)# if there is no overlap, just add it
else:
res[-1][1] = max(i[1], res[-1][1])# here we merge from the end so that res remains sorted
return res
Характерной особенностью решения ниже является запуск списка под названием final параллельно со списком ввода. Прежде чем войти в for петля, final list вставляет в него первый элемент массива. Затем начинается сравнение. Это оно!
def merger(a):
final=[]
final.append(a[0])
for i in range(1,len(a)):
if a[i][0]<=final[-1][1]:
if a[i][1]>final[-1][1]:
low_limit=final[-1][0]
hi_limit=a[i][1]
final.pop()
final.append([low_limit,hi_limit])
if a[i][1]<=final[-1][1]:
low_limit=final[-1][0]
hi_limit=final[-1][1]
final.pop()
final.append([low_limit,hi_limit])
if final[-1][0]<a[i][1]<final[-1][1]:
low_limit=a[i][0]
hi_limit=final[-1][1]
final.pop()
final.append([low_limit,hi_limit])
else:
final.append(a[i])
return final
if __name__=="__main__":
array=[[-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]]
print(merger(array))
Выход:
[[-25, -14], [-10, -3], [2, 6], [12, 18], [22, 30]]