Pythonでいずれかの区間が他の区間に完全に重複しているかどうかを判定する方法

問題の概要

あるイベントの集合について、各区間は開始時刻 a と終了時刻 b のペア (a, b) として表されます。ここでの課題は、与えられた区間の中に「ある区間が別の区間を完全に覆ってしまう（＝別の区間に丸ごと含まれる）」ような組み合わせが存在するかどうかを判定することです。完全な重なりが1つでも見つかれば True を、存在しなければ False を返します。

たとえば、入力が [(4,6), (10,12), (7,9), (13,16)] の場合は、どの区間も他の区間を完全には包含しないため出力は False になります。一方、入力が [(4,6), (4,9), (7,11), (5,8)] の場合は、(5,8) が (4,9) に完全に含まれているため出力は True になります。

解法のアプローチ

この問題は、区間をあらかじめソートしておけば、隣り合う区間同士を比較するだけで効率的に解けます。手順は次の通りです。

• 区間のリストを開始時刻を基準にソートします。
• 2番目の区間から順に、直前の区間と終了時刻を比較します。
• 現在の区間の終了時刻が直前の区間の終了時刻以下であれば、その区間は直前の区間に完全に含まれているため True を返します。
• 最後まで該当するペアが見つからなければ False を返します。

この方法が成り立つのは、ソート後は必ず intervals[i] の開始時刻が intervals[i-1] の開始時刻以上になるため、「終了時刻まで前の区間以下」ということは、その区間が前の区間の内部にすっぽり収まることを意味するからです。

実装例

def solve(intervals):
    intervals.sort()
    for i in range(1, len(intervals)):
        if intervals[i][1] <= intervals[i-1][1]:
            return True
    return False

intervals = [(4,6),(10,12),(7,9),(13,16)]
intervals2 = [(4,6), (4,9), (7,11), (5,8)]

print(solve(intervals))
print(solve(intervals2))

入力

[(4,6),(10,12),(7,9),(13,16)]
[(4,6), (4,9), (7,11), (5,8)]

出力

False
True

動作の解説

1つ目のリスト [(4,6),(10,12),(7,9),(13,16)] をソートすると [(4,6),(7,9),(10,12),(13,16)] となります。隣接する区間を比較しても終了時刻は常に増加していくため、完全な重なりは存在せず False が返されます。

2つ目のリスト [(4,6), (4,9), (7,11), (5,8)] をソートすると [(4,6),(4,9),(5,8),(7,11)] となります。(5,8) の終了時刻 8 は直前の (4,9) の終了時刻 9 以下なので、(5,8) は (4,9) に完全に含まれていると判断され、True が返されます。

注意点：開始時刻が同じ場合の扱い

タプルのデフォルトのソートでは、開始時刻が等しい場合は終了時刻の昇順で並べられます。そのため、(4,6) と (4,9) のように「開始時刻が同じで終了時刻だけ異なる」ペアがあると、小さい方の区間が大きい方に含まれていることを見逃す可能性があります。このケースにも確実に対応したい場合は、開始時刻の昇順・終了時刻の降順でソートすると安全です。

def solve(intervals):
    intervals.sort(key=lambda x: (x[0], -x[1]))
    for i in range(1, len(intervals)):
        if intervals[i][1] <= intervals[i-1][1]:
            return True
    return False

全体の計算量はソートが支配的となるため O(n log n) であり、区間の数が多いデータセットに対しても十分高速に動作します。