範囲のセットがあるとしましょう：
明らかに、これらの範囲は特定のポイントで重複しています。これらの範囲をどのように分析して、元の範囲（この場合は範囲の後の文字）に関連付けられた情報を保持しながら、重複しない範囲のリストを作成しますか？
たとえば、アルゴリズムを実行した後の上記の結果は次のようになります。
オーディオ サンプルをミックスする (部分的にオーバーラップする) プログラムを作成するときに、同じ質問がありました。
私がやったことは、リストに「開始イベント」と「停止イベント」を（アイテムごとに）追加し、リストを時点でソートしてから、順番に処理することでした。時間の代わりに整数ポイントを使用することを除いて、同じことを行うことができます。サウンドを混合する代わりに、範囲に対応するセットに記号を追加します。空の範囲を生成するか、単に省略するかはオプションです。
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))
明らかに、完全にテストされていません。
エンドポイントのリストを作成して並べ替え、開始点と終了点で範囲のリストにインデックスを付けます。次に、並べ替えられたエンドポイントのリストを繰り返し処理し、それぞれについて範囲をチェックして、その時点で開始/停止しているエンドポイントを確認します。
これはおそらくコードでよりよく表現されます...範囲がタプルで表される場合：
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 と rangeInUse は空である必要があり、beginingBoundary は nil である必要があり、usedRanges には、unusedRanges に含まれていたものが含まれている必要があります (ただし、range.end でソートされています)。