Pythonで他の区間に完全に含まれる区間の個数をカウントする方法

問題概要

区間のリストが与えられます。リスト内の各 interval[i] は [start, end](開始値と終了値)を持ちます。この中から、「別の区間に完全に含まれている」区間の個数を求めます。ただし、ある区間が複数の他の区間に含まれている場合でも、1つとしてのみカウントします。

区間 [s0, e0] が別の区間 [s1, e1] の内側にあるとは、s0 ≥ s1 かつ e0 ≤ e1 が成り立つことを指します。

例として、intervals = [[2, 6], [3, 4], [4, 7], [5, 5]] が入力された場合、出力は 2 になります。[3, 4] は [2, 6] に、[5, 5] は [4, 7] にそれぞれ含まれているためです。

解法のアプローチ

この問題は「ソートと最大終了値の追跡」というシンプルな戦略で効率的に解くことができます。手順は以下の通りです。

• 区間リストが空の場合は 0 を返す
• 区間を開始時刻の昇順でソートする。開始時刻が同じ場合は、終了時刻の降順でソートする
• end_mx を負の無限大(-∞)で初期化する
• 答えを格納する ans を 0 で初期化する
• ソート済みリストの各 (start, end) ペアについて以下を繰り返す
  • end ≤ end_mx ならば、ans を 1 増やす(現在の区間は、それまでに処理したいずれかの区間に含まれている)
  • end_mx を end_mx と end の最大値に更新する
• 最後に ans を返す

なぜこの方法が機能するのか

開始時刻の昇順にソートしておけば、現在の区間より先に処理された区間の開始時刻は、必ず現在の区間の開始時刻以下になります。そのため、「これまでに現れた終了時刻の最大値(end_mx)が現在の終了時刻以上であるか」を確認するだけで、包含関係を判定できます。

また、開始時刻が同じ場合に終了時刻の降順でソートしておくことで、同じ開始点を持つ区間同士でも、より長い区間が先に処理され、短い区間が正しくカウントされるようになります。

計算量はソートが支配的となるため、時間計算量は O(n log n)、追加の空間計算量は O(1)(ソートに使用される領域を除く)と非常に効率的です。

実装例

理解を深めるために、以下のPythonによる実装を見てみましょう。

def solve(intervals):
    if not intervals:
        return 0

    intervals.sort(key=lambda x: (x[0], -x[1]))

    end_mx = float("-inf")
    ans = 0

    for start, end in intervals:
        if end <= end_mx:
            ans += 1

        end_mx = max(end_mx, end)

    return ans

intervals = [[2, 6],[3, 4],[4, 7],[5, 5]]
print(solve(intervals))

入力

[[2, 6],[3, 4],[4, 7],[5, 5]]

出力

2