给定一组间隔，我想从一组间隔中找到不重叠的不同间隔。
例如：
输入：[[1,10], [5,20], [6,21], [17,25], [22,23], [24,50] ,[30,55], [60,70]]
输出：[[1,5], [21,22], [23,24], [25,30], [50,55], [60,70]]
我该怎么做？
我目前正在尝试的内容：
gene_bounds_list = [[1,10],[5,20], [6,21],[17,25],[22,23], [24,50],[30,55],[60,70]]
overlap_list = []
nonoverlap_list = []
nonoverlap_list.append(gene_bounds_list[0])
for i in range(1, len(gene_bounds_list)):
curr_gene_bounds = gene_bounds_list[i]
prev_gene_bounds = nonoverlap_list[-1]
if curr_gene_bounds[0]<prev_gene_bounds[0]:
if curr_gene_bounds[1]<prev_gene_bounds[0]: #case1
continue
if curr_gene_bounds[1] < prev_gene_bounds[1]: #case2
nonoverlap_list[-1][0] = curr_gene_bounds[1]
if curr_gene_bounds[1]>prev_gene_bounds[1]:
# previous gene was completely overlapping within current gene,
# so replace previous gene by current (bigger) gene and put previous gene into overlap list
overlap_list.append(nonoverlap_list[-1])
new_bound = [gene_bounds_list[i][0], gene_bounds_list[i][1]]
nonoverlap_list.pop()
nonoverlap_list.append([new_bound[0], new_bound[1]])
elif curr_gene_bounds[0] > prev_gene_bounds[0] and curr_gene_bounds[1] < prev_gene_bounds[1]:
# completely within another gene
overlap_list.append([curr_gene_bounds[0], curr_gene_bounds[1]])
elif curr_gene_bounds[0] < prev_gene_bounds[1]:
# partially overlapping with another gene
new_bound = [nonoverlap_list[-1][1], curr_gene_bounds[1]]
nonoverlap_list[-1][1] = curr_gene_bounds[0]
nonoverlap_list.append([new_bound[0], new_bound[1]])
else:
# not overlapping with another gene
nonoverlap_list.append([gene_bounds_list[i][0], gene_bounds_list[i][1]])
unique_data = [list(x) for x in set(tuple(x) for x in gene_bounds_list)]
within_overlapping_intervals = []
for small in overlap_list:
for master in unique_data:
if (small[0]==master[0] and small[1]==master[1]):
continue
if (small[0]>master[0] and small[1]<master[1]):
if(small not in within_overlapping_intervals):
within_overlapping_intervals.append([small[0], small[1]])
for o in within_overlapping_intervals:
nonoverlap_list.append(o) # append the overlapping intervals
nonoverlap_list.sort(key=lambda tup: tup[0])
flat_data = sorted([x for sublist in nonoverlap_list for x in sublist])
new_gene_intervals = [flat_data[i:i + 2] for i in range(0, len(flat_data), 2)]
print(new_gene_intervals)
但是，这给了我输出：[[1, 5], [6, 10], [17, 20], [21, 22], [23, 24], [25, 30], [50, 55], [60, 70]]
关于如何消除不必要的间隔的任何想法？
这里是一种方法。这个想法是在任何点跟踪间隔的层数。为此，我们在输入间隔时添加一层，而在退出时删除一层。
我们首先构建开始和结束的排序列表。为了确定值是开始还是结束，我们创建元组(start, 1)或(end, -1)。
然后，我们合并这两个列表，按值排序，然后遍历结果列表（使用heapq.merge可以很容易地做到这一点）。每次层数更改为1时，我们都会开始一个不重叠的间隔。当它再次改变时，它就结束了。
from heapq import merge
def non_overlapping(data):
out = []
starts = sorted([(i[0], 1) for i in data]) # start of interval adds a layer of overlap
ends = sorted([(i[1], -1) for i in data]) # end removes one
layers = 0
current = []
for value, event in merge(starts, ends): # sorted by value, then ends (-1) before starts (1)
layers += event
if layers ==1: # start of a new non-overlapping interval
current.append(value)
elif current: # we either got out of an interval, or started an overlap
current.append(value)
out.append(current)
current = []
return out
data = [[1,10], [5,20], [6,21], [17,25], [22,23], [24,50] ,[30,55], [60,70]]
non_overlapping(data)
# [[1, 5], [21, 22], [23, 24], [25, 30], [50, 55], [60, 70]]
请注意，您在问题中输入的预期答案是错误的（例如，它包含的45不是输入数据的一部分）
在时间线上绘制时间间隔。由于范围仅为10**5，因此可以使用内存。绘图和扫描可以在线性时间内完成。
intervals = [[1,10], [5,20], [6,21], [17,25], [22,23], [24,50] ,[30,55], [60,70]]
max_ = max(intervals, key=lambda x: x[1])[1]
timeline = [0] * (max_ + 1)
# mark plots
for start, end in intervals:
timeline[start] += 1
timeline[end] -= 1
# make the timeline
for i in range(1, len(timeline)):
timeline[i] += timeline[i - 1]
# scan
result = []
for i, item in enumerate(timeline):
if i == 0:
continue
prev = timeline[i - 1]
if item == 1 and prev != 1:
result.append([i, i + 1])
elif item == 1 and prev == 1:
result[-1][1] = i + 1
end = i
print(result)
编辑：由于范围已更新为〜10^8，因此将无法使用。