如何划分的一组重叠的范围为不重叠的范围？ [英] How to divide a set of overlapping ranges into non-overlapping ranges?

问题描述

假设你有一组范围：

• 在0 - 100：'A'
• 在0 - 75：'B'
• 在95 - 150：'C'
• 在120 - 130：D

显然，这些范围重叠在某些点。你会如何​​解剖这些范围，以产生非重叠的范围的列表，而与它们的原始范围相关联保持的信息（在这种情况下，范围后的字母）？

Obviously, these ranges overlap at certain points. How would you dissect these ranges to produce a list of non-overlapping ranges, while retaining information associated with their original range (in this case, the letter after the range)?

例如，在上述的运行算法将是后的结果：

For example, the results of the above after running the algorithm would be:

• 在0 - 75：'A'，'B'
• 在76 - 94：'A'
• 在95 - 100：'A'，'C'
• 在101 - 119：'C'
• 在120 - 130：'C'，'D'
• 在131 - 150：'C'

推荐答案

我写一个程序混合（部分重叠）音频采样时，也有同样的问题。

I had the same question when writing a program to mix (partly overlapping) audio samples.

我所做的是增加一个启动事件和停止活动（每个项目）到一个列表，列表排序按时间点，然后才能对其进行处理。你可以做同样的，除了使用时间的整点，而不是物，而不是混合的声音你会添加符号对应于一定范围内设定。无论你产生空范围，或只是忽略它们将是可选的。

What I did was add an "start event" and "stop event" (for each item) to a list, sort the list by time point, and then process it in order. You could do the same, except using an integer point instead of a time, and instead of mixing sounds you'd be adding symbols to the set corresponding to a range. Whether you'd generate empty ranges or just omit them would be optional.

修改也许有些code ...

Edit Perhaps some code...

# 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))

完全未经测试，效果显着。

Totally untested, obviously.

这篇关于如何划分的一组重叠的范围为不重叠的范围？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！