假设您有一组范围:
- 0 - 100: 'a'
- 0 - 75: 'b'
- 95 - 150: 'c'
- 120 - 130: 'd'
显然,这些范围在某些点重叠。您将如何剖析这些范围以生成一个非重叠范围列表,同时保留与其原始范围相关的信息(在本例中为范围后面的字母)?
例如,上述算法运行后的结果为:
- 0 - 75: 'a', 'b'
- 76 - 94:'a'
- 95 - 100:“a”、“c”
- 101 - 119: 'c'
- 120 - 130: 'c', 'd'
- 131 - 150: 'c'
最佳答案
我在编写混合(部分重叠)音频样本的程序时遇到了同样的问题。
我所做的是将“开始事件”和“停止事件”(针对每个项目)添加到列表中,按时间点对列表进行排序,然后按顺序进行处理。您可以这样做,除了使用整数点而不是时间,而不是混合声音,您将向对应于范围的集合添加符号。您是生成空范围还是只是忽略它们都是可选的。
编辑
也许一些代码...
# input = list of (start, stop, symbol) tuples
points = [] # list of (offset, plus/minus, symbol) tuples
for start,stop,symbol in input:
points.append((start,'+',symbol))
points.append((stop,'-',symbol))
points.sort()
ranges = [] # output list of (start, stop, symbol_set) tuples
current_set = set()
last_start = None
for offset,pm,symbol in points:
if pm == '+':
if last_start is not None:
#TODO avoid outputting empty or trivial ranges
ranges.append((last_start,offset-1,current_set))
current_set.add(symbol)
last_start = offset
elif pm == '-':
# Getting a minus without a last_start is unpossible here, so not handled
ranges.append((last_start,offset-1,current_set))
current_set.remove(symbol)
last_start = offset
# Finish off
if last_start is not None:
ranges.append((last_start,offset-1,current_set))
显然,完全未经测试。
关于python - 如何将一组重叠范围划分为非重叠范围?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/628837/