数値の範囲を示す複数のリストのオーバラップしている数の最大値とその範囲を計算したい

Question

ある数の範囲を示す２つの実数（left<right）からなるリスト[left_i, right_i]（i＝0, 1, 2・・）のリスト[[left_0, right_0],[left_1, right_1],[left_2, right_2],・・・] において、重なり合う部分の数の最大値を求めるコードを書こうとしています。
下記は、サンプルです。
a= [[-1.0, 20.0], [0.0, 14.0], [2.0, 3.0], [4.0, 9.0], [8.0, 15.0], [9.5, 15.0], [11.0, 14.0], [13.0, 14.0]]
ソートしたうえで、左から重なる部分を順次更新していくコードを書いたのですが、そうすると、上記のデータの場合、「3」という答えになり、「6」という正解にはなりません。
各範囲の組合せの全検索をして最大値を求めれば答えは出るのでしょうけれど、全検索以外の解法が思いつきません。全検索以外の方法で計算する考え方があれば教えてください。

hani_list = [[-1.0, 20.0], [0.0, 14.0], [2.0, 3.0], [4.0, 9.0], [8.0, 15.0], [9.5, 15.0], [11.0, 14.0], [13.0, 14.0]]
hani_list = sorted(hani_list)
cnt = 0
max_cnt = 0
flag = 0
history = []
for i, one in enumerate(hani_list):
    
    if i == 0:
        left, right = one[0], one[1]
        cnt += 1

    else:
        if one[1] < right:
            left, right = one[0], one[1]           
            cnt += 1
            if max_cnt < cnt:max_cnt = cnt
            
        elif right <= one[1] and one[0] < right:
            left = one[0]
            cnt += 1
            if max_cnt < cnt:max_cnt = cnt

            
        elif right < one[0]:
            history.append([left, right, cnt])
            left, right = one[0], one[1]
            cnt = 1

history.append([left, right, cnt])

print('max_cnt:', max_cnt)
print(history)
#max_cnt: 3
#[[2.0, 3.0, 3], [8.0, 9.0, 2], [13.0, 14.0, 3]]

Answer 1

考え方としては区間スケジューリング問題の類似問題や一次元領域の重なり検出のアルゴリズムについての質問です。の回答が分かりやすいと思います。
実装コードとしてはC言語　直線状の線分の重複回数を求めるアルゴリズムが参考になります。

その範囲を計算したい

タイトル見逃していました。重なる範囲も得られるようにしました。

from collections import namedtuple
from functools import cmp_to_key

# 端点の比較関数
def compEnds( p1, p2):
    if p1.x < p2.x:
        return -1
    if p1.x > p2.x:
        return 1

    ret = 0
    if p1.isLeft and (not p2.isLeft):
        ret = 1
    if (not p1.isLeft) and p2.isLeft:
        ret = -1

    ret *= -1 # 開区間（右端＝左端は重ならないとみなす）ならコメントに

    return ret

def getMaxOverlaps( hani_list):

    # 端点データのセットアップ
    End = namedtuple('end', ('x', 'isLeft', 'srcPos'))
    ends = []
    for i, hani in enumerate(hani_list):
        ends.append( End(hani[0], True, i))
        ends.append( End(hani[1], False,i))

    # 端点データのソート
    ends = sorted(ends, key=cmp_to_key(compEnds))

    # 重なりを求める
    maxOverlaps = 0
    currentOverlaps = 0
    curRanges = set()
    maxRanges = set()
    for end in ends:
        if end.isLeft:
            currentOverlaps += 1
            curRanges.add(end.srcPos)
            if currentOverlaps > maxOverlaps:
                maxOverlaps = currentOverlaps
                maxRanges = curRanges.copy()
        else:
            currentOverlaps -= 1
            curRanges.remove(end.srcPos)

    maxRanges = [hani_list[n] for n in sorted(maxRanges)]

    return maxOverlaps, maxRanges

hani_list = [[-1.0, 20.0], [0.0, 14.0], [2.0, 3.0], [4.0, 9.0], [8.0, 15.0], [9.5, 15.0], [11.0, 14.0], [13.0, 14.0]]
ret = getMaxOverlaps( hani_list)
print(ret) # (6, [[-1.0, 20.0], [0.0, 14.0], [8.0, 15.0], [9.5, 15.0], [11.0, 14.0], [13.0, 14.0]])

hani_list = [[1, 2], [2, 3], [3, 4]]
ret = getMaxOverlaps( hani_list)
print(ret) # (2, [[1, 2], [2, 3]])

Comments

[yoshikazu.egawa]

類似質問の紹介をありがとうございました。勉強させていただきます。

Answer 2

1. まずは、オーバーラップの最大段数を計算する
2. オーバーラップが最大段数になる範囲を調べる

という2パスで考えると楽なのではないかと思います。

まず、下準備としてhani_listを始点と終点のイベントに分割してソートしておきます。
これを始点・終点のイベントを数直線の左から順にチェックできるようにします。

step1:
イベントを順に調べて、始点であればnest_levelを+1、終点であれば-1します。
nest_levelの最大値は、max_levelとして記録に残しておくことにします。

step2:
イベントリストをもう一度順に流して、nest_levelがmax_levelと等しくなる部分が求めたい期間の始点、
nest_levelがmax_level-1になる部分を終点として記録します。

hani_list = [[-1.0, 20.0], [0.0, 14.0], [2.0, 3.0], [4.0, 9.0],
             [8.0, 15.0], [9.5, 15.0], [11.0, 14.0], [13.0, 14.0]]

# 下準備
events = []
for s, e in hani_list:
    events.append((s, +1))
    events.append((e, -1))

# step1: オーバーラップの最大段数を調べる
max_level = 0
nest_level = 0
for _, ev in sorted(events):
    nest_level += ev
    max_level = max(max_level, nest_level)

# step2: 最大段数になる期間を調べる
ans = []
st = None
for t, ev in sorted(events):
    if ev == 1:
        nest_level += 1
        if nest_level == max_level:
            st = t
    else:
        nest_level -= 1
        if nest_level == max_level - 1:
            ans.append([st, t])

print(max_level)
print(ans)

Comments

[yoshikazu.egawa]

丁寧でわかりやすい説明をありがとうございました。よく理解できました。