假设您有一组范围：
显然，这些范围在某些点上是重叠的。您将如何剖析这些范围以生成不重叠范围的列表，同时保留与其原始范围相关的信息（在本例中为范围后面的字母）？
例如，上述算法运行后的结果将是：
在编写混合（部分重叠）音频样本的程序时，我也遇到了同样的问题。
我所做的是将“开始事件”和“停止事件”（针对每个项目）添加到列表中，按时间点对列表进行排序，然后按顺序处理它。您可以做同样的事情，除了使用整数点而不是时间，并且您可以将符号添加到与范围相对应的集合中，而不是混合声音。无论您是生成空范围还是忽略它们都是可选的。
Edit# 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))
显然完全未经测试。
与 Edmunds 类似的答案，经过测试，包括对 (1,1) 等区间的支持：
class MultiSet(object):
def __init__(self, intervals):
self.intervals = intervals
self.events = None
def split_ranges(self):
self.events = []
for start, stop, symbol in self.intervals:
self.events.append((start, True, stop, symbol))
self.events.append((stop, False, start, symbol))
def event_key(event):
key_endpoint, key_is_start, key_other, _ = event
key_order = 0 if key_is_start else 1
return key_endpoint, key_order, key_other
self.events.sort(key=event_key)
current_set = set()
ranges = []
current_start = -1
for endpoint, is_start, other, symbol in self.events:
if is_start:
if current_start != -1 and endpoint != current_start and \
endpoint - 1 >= current_start and current_set:
ranges.append((current_start, endpoint - 1, current_set.copy()))
current_start = endpoint
current_set.add(symbol)
else:
if current_start != -1 and endpoint >= current_start and current_set:
ranges.append((current_start, endpoint, current_set.copy()))
current_set.remove(symbol)
current_start = endpoint + 1
return ranges
if __name__ == '__main__':
intervals = [
(0, 100, 'a'), (0, 75, 'b'), (75, 80, 'd'), (95, 150, 'c'),
(120, 130, 'd'), (160, 175, 'e'), (165, 180, 'a')
]
multiset = MultiSet(intervals)
pprint.pprint(multiset.split_ranges())
[(0, 74, {'b', 'a'}),
(75, 75, {'d', 'b', 'a'}),
(76, 80, {'d', 'a'}),
(81, 94, {'a'}),
(95, 100, {'c', 'a'}),
(101, 119, {'c'}),
(120, 130, {'d', 'c'}),
(131, 150, {'c'}),
(160, 164, {'e'}),
(165, 175, {'e', 'a'}),
(176, 180, {'a'})]
我想说创建一个端点列表并对其进行排序，还按起点和终点对范围列表进行索引。然后遍历已排序端点的列表，并针对每个端点检查范围以查看哪些端点在该点开始/停止。
如果您的范围由元组表示，这可能在代码中更好地表示：
ranges = [(0,100,'a'),(0,75,'b'),(95,150,'c'),(120,130,'d')]
endpoints = sorted(list(set([r[0] for r in ranges] + [r[1] for r in ranges])))
start = {}
end = {}
for e in endpoints:
start[e] = set()
end[e] = set()
for r in ranges:
start[r[0]].add(r[2])
end[r[1]].add(r[2])
current_ranges = set()
for e1, e2 in zip(endpoints[:-1], endpoints[1:]):
current_ranges.difference_update(end[e1])
current_ranges.update(start[e1])
print '%d - %d: %s' % (e1, e2, ','.join(current_ranges))
尽管回想起来，如果没有更有效（或至少看起来更干净）的方法来做到这一点，我会感到惊讶。
您所描述的是集合论的一个例子。有关计算集合的并集、交集和差集的通用算法，请参阅：
www.gvu.gatech.edu/~jarek/graphics/papers/04PolygonBooleansMargalit.pdf
虽然本文针对的是图形，但它也适用于一般集合论。不完全是轻松阅读材料。
伪代码：
unusedRanges = [ (each of your ranges) ]
rangesInUse = []
usedRanges = []
beginningBoundary = nil
boundaries = [ list of all your ranges' start and end values, sorted ]
resultRanges = []
for (boundary in boundaries) {
rangesStarting = []
rangesEnding = []
// determine which ranges begin at this boundary
for (range in unusedRanges) {
if (range.begin == boundary) {
rangesStarting.add(range)
}
}
// if there are any new ones, start a new range
if (rangesStarting isn't empty) {
if (beginningBoundary isn't nil) {
// add the range we just passed
resultRanges.add(beginningBoundary, boundary - 1, [collected values from rangesInUse])
}
// note that we are starting a new range
beginningBoundary = boundary
for (range in rangesStarting) {
rangesInUse.add(range)
unusedRanges.remove(range)
}
}
// determine which ranges end at this boundary
for (range in rangesInUse) {
if (range.end == boundary) {
rangesEnding.add(range)
}
}
// if any boundaries are ending, stop the range
if (rangesEnding isn't empty) {
// add the range up to this boundary
resultRanges.add(beginningBoundary, boundary, [collected values from rangesInUse]
for (range in rangesEnding) {
usedRanges.add(range)
rangesInUse.remove(range)
}
if (rangesInUse isn't empty) {
// some ranges didn't end; note that we are starting a new range
beginningBoundary = boundary + 1
}
else {
beginningBoundary = nil
}
}
}
单元测试：
最后，resultRanges 应该有您要查找的结果，unusedRanges 和rangesInUse 应该为空，beginningBoundary 应该为nil，usedRanges 应该包含unusedRanges 曾经包含的内容（但按range.end 排序）。
这是使用 pandas 库的解决方案。该函数将可能重叠的范围分割成不重叠的子范围；并跟踪哪些范围包含每个子范围。这个答案基于这里和这里找到的算法。
import pandas as pd
def split_overlapping_ranges(df, lb, ub, range_id=None):
"""Split ranges that may overlap into non-overlapping sub-ranges.
Keep track of which ranges contain each subrange."""
# ensure range_id meets our high standards
if range_id is None:
range_id = 'range_id'
df[range_id] = range(len(df.index))
elif df.duplicated(subset=[range_id]).any():
raise ValueError('range_id contains duplicate values')
# reshape ranges to get subranges
df2 = pd.concat([df.drop(columns=[ub])
.assign(is_upper_bound=-1), # -1 = False; 1 = True
df.drop(columns=[lb])
.rename(columns={ub: lb})
.assign(is_upper_bound=1)])
df2 = df2.sort_values([lb, 'is_upper_bound'])
df2[ub] = df2[lb].shift(-1) # the next bound is the new upper bound
# drop ranges that are gaps (where the lower bound is an endpoint and the upper bound
# is a start point, and the range is not contained within another range)
df2['overlaps_w_next_row'] = df2['is_upper_bound'].cumsum() < 0
df2 = df2[df2['overlaps_w_next_row']].drop(columns=['overlaps_w_next_row'])
# get containing intervals (for each subrange x, get list of range(s) which contain x)
def get_containing_intervals(df2row):
intervals = []
for index, dfrow in df.iterrows():
if (dfrow[lb] <= df2row[lb]) & (df2row[ub] <= dfrow[ub]):
intervals.append(dfrow[range_id])
return intervals
df2[range_id] = df2.apply(lambda row: get_containing_intervals(row), axis=1)
# delete artificial singletons created when multiple ranges share a bound
df2['is_single_val'] = df2[lb]==df2[ub]
df2['range_id_str'] = df2[range_id].astype(str)
df2 = (df2.sort_values(['range_id_str', 'is_single_val'])
.drop_duplicates(subset=['range_id_str', lb])
.drop_duplicates(subset=['range_id_str', lb])
.drop(columns=['is_upper_bound', 'is_single_val', 'range_id_str'])
.sort_values([lb, ub])
.reset_index(drop=True))
return df2
if __name__=="__main__":
lb = 'lower_bound'
ub = 'upper_bound'
df = pd.DataFrame(data={'rangelabel': ['A', 'B', 'C', 'D'],
lb: [0, 0, 95, 120],
ub: [100, 75, 150, 130]})
newdf = split_overlapping_ranges(df, lb, ub, 'rangelabel')
print(df)
print(newdf)
输出：
rangelabel lower_bound upper_bound
0 A 0 100
1 B 0 75
2 C 95 150
3 D 120 130
rangelabel lower_bound upper_bound
0 [A, B] 0 75.0
1 [A] 75 95.0
2 [A, C] 95 100.0
3 [C] 100 120.0
4 [C, D] 120 130.0
5 [C] 130 150.0